具有移动约束的网格探索算法 [英] Grid exploring algorithm with move constraints

问题描述

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

Lately I've been stuck on an algorithm for "exploring a grid". I want to paint all moves that are valid within a certain part of a grid based on a starting square that could be anywhere on the grid. My original plan was to use recursive split off in 4 directions marking grids until it either reached a boundary or the move limit. An exploring "branch" cannot move diagonally:

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

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我做了一个快速运行的程序样本此处，其中算法被卡在值之间，直到触发运行时错误。

I know this algorithm doesn't work b/c I did a quick runnable sample here where the algorithm gets stuck between values until it triggers a Runtime error.

因此，在这一点上：

1. 递归仍然可能（切换到迭代）？

1. Is recursion still a possibility (switch to iterative)?

是否有更好的替代算法来解决此问题？

Is there a better alternative algorithm to this problem?

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

Is my algorithm close, but needs a few tweaks?

推荐答案

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

You seem to be looking to implement depth-first search. The wiki article even provides some pseudo code which you can use to implement the algorithm.

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

Note that this will mark all reachable squares, but will not print out all (redundant) moves unless you modify the algorithm.

这篇关于具有移动约束的网格探索算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！