带移动约束的网格探索算法

Question

最近，我一直被困在“探索网格”的算法上。我想根据网格上可能位于任何位置的起始正方形绘制网格中特定部分内所有有效的移动。我最初的计划是在4个方向上使用递归分割来标记网格，直到它达到边界或移动限制。探索“分支”不能沿对角线移动：

*注意：箭头不代表堆栈中的发生，它们用于可视化算法的概念

private void Explore(byte moves, byte row, char col) {
        if (row >= Grid[0].Count || col >= Grid.Count || row + col + 2 > moves) {//var < 0 handled b/c byte b = 0; (byte)(b-1) == 255
            return;
        }
        Grid[row][col].color = ...;//mark it

        if (Grid[row + 1][col + 1] == notVisited) Explore((byte) (moves - 1), (byte)(row + 1), (char) (col + 1));
        if (Grid[row - 1][col + 1]== notVisited) Explore((byte)(moves - 1), (byte)(row - 1), (char) (col + 1));
        if (Grid[row - 1][col - 1] == notVisited) Explore((byte)(moves - 1), (byte)(row - 1), (char) (col - 1));
        if (Grid[row + 1][col - 1] == notVisited) Explore((byte)(moves - 1), (byte)(row + 1), (char) (col - 1));
    }

我知道这种算法在b/c模式下不起作用。我在这里做了一个快速的可运行示例，算法在值之间卡住，直到触发运行时错误。

所以在这一点上：

> < li>

递归仍然是可能的吗(切换到迭代)？

有没有更好的替代算法来解决这个问题？

我的算法是否接近，但需要一些调整？

Answer 1

搜索的想法应该可以正常工作，但代码不起作用的原因是它正在检查对角线。

if (Grid[row + 1][col + 1] == notVisited)
if (Grid[row - 1][col + 1]== notVisited) 
if (Grid[row - 1][col - 1] == notVisited) 
if (Grid[row + 1][col - 1] == notVisited)

我想你的意思是:

if (Grid[row + 1][col] == notVisited)
if (Grid[row - 1][col]== notVisited) 
if (Grid[row][col + 1] == notVisited) 
if (Grid[row][col - 1] == notVisited)

对于问题：

1： 递归很好。迭代会更快，但不会产生太大的影响。

2:可能有很多不同的方法，但目前的方法应该没问题。

3： 除了改变这四个条件之外

|| row + col + 2 > moves)

可能会导致程序运行异常，具体取决于其放置位置。对于所有递归路径，moves 参数都不相同，因此大多数时候程序可能会绘制整个网格。除此之外，程序应该运行正常。

Answer 2

您似乎正在寻求实现深度优先搜索。wiki文章甚至提供了一些伪代码，您可以使用它们来实现该算法。

请注意，这将标记所有可到达的方块，但除非修改算法，否则不会打印出所有（冗余）移动。