我最近玩了一个名为Just A Trim Please的小 Flash 游戏,我非常喜欢整个概念。
游戏的基本目标是通过每个方格一次修剪整个草坪。您的割草机从瓷砖开始,您可以从那里向各个方向移动(除了有墙挡住您的地方)。如果您多次在草地瓷砖上奔跑,它会恶化并且您将失去关卡。您只能向左、向右、向上或向下移动。但是,当您完成游戏时,会添加更多图块:
- 您只能修剪一次的瓷砖(草)。
- 在恶化之前可以运行两次的瓷砖(更高的草)。
- 一条你可以随心所欲地翻越的领带(混凝土)。
- 一块你不能翻过的瓷砖(一堵墙)。
如果你不明白我的意思,去玩游戏,你会明白的。
我设法编写了一个蛮力算法,它可以只用第一种瓷砖来解决难题(这基本上是骑士巡回赛问题的变体)。然而,这不是最佳的,只适用于只能运行一次的拼图。我完全不知道如何处理额外的瓷砖。
给定一个起点和一个瓦片图,有没有办法或算法来找到解决关卡的路径(如果可以解决的话)?我不在乎效率,这只是我想到的一个问题。我很好奇你必须如何去解决它。
我不是在寻找代码,只是在寻找指导方针,或者如果可能的话,是对该过程的纯文本解释。但是,如果您确实有伪代码,请分享!:)
(另外,我不完全确定这是否与寻路有关,但这是我最好的猜测。)