等级求解和寻路

Question

我最近玩了一个名为Just A Trim Please的小游戏,真的很喜欢整个概念.

游戏的基本目标是通过遍历每个广场一次来修剪整个草坪.您的割草机从瓷砖开始,从那里您可以向各个方向移动(除非墙壁阻挡您).如果你不止一次在草地上跑,它会恶化,你会失去水平.您只能向左,向右,向上或向下移动.但是,当您完成游戏时,会添加更多图块:

• 一块瓷砖,你只能割一次(草).
• 瓷砖你可以在它变质之前跑两次(更高的草).
• 一个TIIE你可以去了,只要你想尽可能多的(混凝土).
• 你无法翻过的瓷砖(墙).

如果你没理解我的意思,去玩游戏,你会明白的.

我设法编写了一个蛮力算法,它可以解决只有第一种瓦片的谜题(这基本上是Knight's Tour问题的变体).然而,这不是最佳的,只适用于只能运行一次的瓷砖拼图.我完全迷失了如何处理额外的瓷砖.

给定一个起点和一个瓦片地图,有没有办法或算法来找到解决水平的路径(如果可以解决)？我不关心效率,这只是我心中的一个问题.我很好奇你怎么去解决它.

我不是在寻找代码,只是指南,或者如果可能的话,还要查看程序的纯文本说明.如果你确实有伪代码,那么请分享!:)

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

Answer 1

问题是有限的,所以,确实有一个算法.

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

如果你想减少额外的瓷砖(较高的草和混凝土)到标准草,你可以像这样:

• 每个连续的混凝土块首先被缩减为单个图形顶点,然后移除顶点,因为混凝土块区域实际上只是一种移动到达其他图块的方式.
• 每个较高的草瓦被替换为两个顶点,这两个顶点连接到原始邻居,但不相互连接.

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

G G T
G C T
C C G

将其视为图表:

现在改变混凝土块.首先将它们缩小为一个(因为它们全部连接在一起):

然后删除顶点,连接"通过"它:

然后展开高草砖,将副本连接到与原件相同的节点.

然后用G代替T,T'.你现在有一个不再是矩形网格的图形,但它只包含草节点.

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