algorithm - 关卡求解和寻路

Question

我最近玩了一个叫做 Just A Trim Please 的小 flash 游戏并且非常喜欢整个概念。

游戏的基本目标是通过遍历每个方格一次来修剪整个草坪。你的割草机从一 block 瓷砖开始，你可以从那里向各个方向移动(除了有墙壁挡住你的地方)。如果你在草地上跑不止一次，它就会变质，你就会失去水平。您只能向左、向右、向上或向下移动。但是，当您完成游戏时，会添加更多图 block :

• 您只能修剪一次(草)的瓷砖。
• 您可以在其劣化(更高的草)之前跑过 两次 的瓷砖。
• 您可以尽可能多地(具体)。
• 一 block 你不能越过的瓷砖(一堵墙)。

如果你不明白我的意思，去玩游戏你就会明白。

我设法编写了一个暴力算法，可以只用第一种瓷砖解决难题(这基本上是 Knight's Tour 问题的变体)。然而，这并不是最优的，并且只适用于带有只能运行一次的拼图的拼图。我完全不知道如何处理额外的瓷砖。

给定一个起点和一张瓦片 map ，是否有一种方法或算法可以找到解决该关卡的路径(如果可以解决)？我不关心效率，这只是我想到的一个问题。我很好奇你将如何去解决它。

我不是在寻找代码，只是在寻找指南，或者如果可能的话，对过程的纯文本解释。但是，如果您确实有伪代码，那么请分享! :)

(另外，我不完全确定这是否与寻路有关，但这是我最好的猜测。)

Answer 1

问题是有限的，所以当然有算法。

非确定性算法可以通过猜测正确的着法然后验证它们是否有效来轻松解决问题。该算法可以通过使用例如回溯搜索来确定。

如果您想将额外的地 block (高草和混凝土)减少为标准草地，您可以这样做:

• 每个连续的混凝土 block 首先被简化为一个图形顶点，然后删除该顶点，因为混凝土 block 区域实际上只是一种移动以到达其他方 block 的方式。
• 每个较高的草方 block 都被替换为与原始邻居相连但彼此不相连的两个顶点。

示例:G = 草，T = 高草，C = 混凝土

G G T
G C T
C C G

将其视为图表:

现在把混凝土 block 移开。首先将它们缩小为一个(因为它们都是相连的):

然后删除顶点，“通过”它连接:

然后展开高草方 block ，将副本连接到与原始方 block 相同的节点。

然后将 T、T' 替换为 G。您现在拥有一个不再是矩形网格但仅包含草节点的图形。

当且仅当原始问题可以解决时，转换后的问题才能解决，并且您可以将转换后问题的解决方案转换为原始问题的解决方案。