5

我最近玩了一个名为Just A Trim Please的小 Flash 游戏，我非常喜欢整个概念。

游戏的基本目标是通过每个方格一次修剪整个草坪。您的割草机从瓷砖开始，您可以从那里向各个方向移动（除了有墙挡住您的地方）。如果您多次在草地瓷砖上奔跑，它会恶化并且您将失去关卡。您只能向左、向右、向上或向下移动。但是，当您完成游戏时，会添加更多图块：

  • 您只能修剪一次的瓷砖（草）。
  • 在恶化之前可以运行两次的瓷砖（更高的草）。
  • 一条你可以随心所欲地翻越的领带（混凝土）。
  • 一块你不能翻过的瓷砖（一堵墙）。

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

我设法编写了一个蛮力算法，它可以只用第一种瓷砖来解决难题（这基本上是骑士巡回赛问题的变体）。然而，这不是最佳的，只适用于只能运行一次的拼图。我完全不知道如何处理额外的瓷砖。

给定一个起点和一个瓦片图，有没有办法或算法来找到解决关卡的路径（如果可以解决的话）？我不在乎效率，这只是我想到的一个问题。我很好奇你必须如何去解决它。

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

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

4

2 回答 2

6

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

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

如果您想将额外的瓷砖（较高的草和混凝土）减少到标准草，您可以这样做：

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

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

G G T
G C T
C C G

将其视为图形：

在此处输入图像描述

现在把混凝土块改掉。首先将它们缩小为一个（因为它们都是连接的）：

在此处输入图像描述

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

在此处输入图像描述

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

在此处输入图像描述

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

在此处输入图像描述

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

于 2013-08-22T07:33:33.927 回答
1

旅行推销员有一种 DP方法。

也许您可以修改它（随着添加更多部分重新计算）。对于一块长草，您也许可以将其分成两个节点，因为您必须访问它两次。然后将两个节点重新连接到它周围的节点。

于 2013-08-22T02:50:12.020 回答