arrays - 遍历二维数组中可能的每个单元格

Question

我不知道该怎么称呼这个问题，但我确定它有一个名字。否则找到答案会更简单。

给定一个单元格的“ map ”，例如:

O - - -
- X - -
- X X -
- - - -

其中 O = 起始位置，X = 障碍物，- = 未访问。我想遍历这张 map (我已将其存储为 2D 数组)并访问尽可能多的单元格而不触及已访问的单元格。

我的算法如下:

如果我能向右走，就向右走。

否则，如果我能下去，就下去。

否则，如果我可以向左走，就向左走。

否则，如果我能上去，就上去。

如果我卡住了，回溯并将那个单元格标记为“不可访问”，然后返回到 1。

所以有两个问题:

对于较大的 map ，障碍物的数量和放置位置通常会导致我的算法无法到达很多单元格。我尝试了步骤 1-4 的不同顺序(即，如果可以的话，总是向上等)，但这显然取决于给定的 map 。

我不知道什么时候停下来。如果我的算法到达“终点”，即我实际上已经访问了每个可能的单元格，它不会停止，只是一直回溯到起点。

所以我想我的问题是:有没有更好的方法来实现这个，或者我如何调整我当前的算法来解决这个问题？

Answer 1

由于以下情况，您的算法不起作用:

O - - -
X - - X

因为你的算法首先会一直正确

O 1 2 3
X - - X

并在回溯时将最右边的单元格标记为阻塞，因此它永远不会找到最佳的

O 1 4 5
X 2 3 X

您可以通过将其视为图形问题并简单地应用任何最长路径算法(通常是 NP-hard)以通用方式解决此问题，但我不确定您是否熟悉这种方法。

一种可能更简单的查看方法是:

跟踪当前位置以及您为到达该位置所采取的所有步骤。

对于每个位置，您最终都会尝试按照右 (R)、下 (D)、左 (L)、上 (U) 的顺序向各个方向迈进。

当您尝试了某个位置的所有方向(即您尝试了 U)时，通过执行您所做的最后一步的逆向后退一步。

一个例子可能会有所帮助。让我们再次考虑同样的例子。我将 C 用于当前位置，将 # 用于访问过的单元格。在回溯的情况下，我们跟踪移动堆栈和最后一步。

C - - -  Stack: []
X - - X  Backtracked move: -

向右走

# C - -  Stack: [R]
X - - X  Backtracked move: -

向右走

# # C -  Stack: [R, R]
X - - X  Backtracked move: -

向右走

# # # C  Stack: [R, R, R]
X - - X  Backtracked move: -

尝试向右、向下、向左和向上，注意你被卡住并回溯，即取右(左)的相反方向

# # C -  Stack: [R, R]
X - - X  Backtracked move: R

上次回溯的 Action 是对的，所以现在尝试下一步，即下台

# # # -  Stack: [R, R, D]
X - C X  Backtracked move: -

向右试，向下试，向左走

# # # -  Stack: [R, R, D, L]
X C # X  Backtracked move: -

又卡住了，所以回溯

# # # -  Stack: [R, R, D]
X - C X  Backtracked move: L

最后一个回溯的 Action 被留下了，所以现在尝试下一个 Action ，即尝试。请注意，我们被卡住并进一步回溯。

快进到第一个有趣的下一步:

# C - -  Stack: [R]
X - - X  Backtracked move: R

最后一个是对的，所以继续向下。

# # - -  Stack: [R, D]
X C - X  Backtracked move: -

你现在可能明白了，所以我只是一路快进:

# # # C  Stack: [R, D, R, U, R]
X # # X  Backtracked move: -

并一路回溯:

C - - -  Stack: []
X - - X  Backtracked move: R

最后一步是正确的，所以尝试向下、向左和向上。你完成了。

一路上，您会记录您所见过的最长路径，这就是您的答案。