C#递归，“数据结构与算法”。这个程序如何打印单独的路径而不覆盖自己？

Question

C#递归，“数据结构与算法”。这个程序如何打印单独的路径而不覆盖自己？

3

我正在阅读Alfred V. Aho和Jeffrey D. Ullman的《数据结构与算法》中关于C#递归的部分。链接

这个问题旨在加深对递归的理解。

我们有一个矩形迷宫，由N*M个方块组成。

每个方块要么可通过，要么不可通过。冒险家从左上角（即入口）进入迷宫，必须到达迷宫的右下角（即出口）。

在每一步中，冒险家可以向上、向下、向左或向右移动一个位置，但他不能越过迷宫的边界或踏上不可通过的方块。也禁止通过同一位置多次走过（如果几步后回到已经到达的位置，则认为冒险家迷路了）。

以下程序使用递归在控制台中打印出所有可能的迷宫路径。

一个二维字符数组表示迷宫，字符' '（空格）标记可通过的位置，'*'标记不可通过的位置，'e'是迷宫的出口。我们已经访问过的位置用字符's'标记。数组"path[]"用于存储和打印我们通过递归算法找到的路径，每个方向都记录为(L-左，U-上，R-右，D-下)。计数器跟踪我们递归地移动到下一个位置的次数，即递归的当前深度。

class Program
{
    static char[,] lab =
    {
      {' ', ' ', ' ', '*', ' ', ' ', ' '},
      {'*', '*', ' ', '*', ' ', '*', ' '},
      {' ', ' ', ' ', ' ', ' ', ' ', ' '},
      {' ', '*', '*', '*', '*', '*', ' '},
      {' ', ' ', ' ', ' ', ' ', ' ', 'e'},
    };

    static char[] path = new char[lab.GetLength(0) * lab.GetLength(1)];
    static int position = 0;

    static void FindPath(int row, int col, char direction)
    {
        if ((col < 0) || (row < 0) ||
            (col >= lab.GetLength(1)) || (row >= lab.GetLength(0)))
        {
            // We are out of the labyrinth
            return;
        }

        // Append the direction to the path
        path[position] = direction;
        position++;

        // Check if we have found the exit
        if (lab[row, col] == 'e')
        {
            PrintPath(path, 1, position - 1);
        }

        if (lab[row, col] == ' ')
        {
            // The current cell is free. Mark it as visited
            lab[row, col] = 's';

            // Invoke recursion to explore all possible directions
            FindPath(row, col - 1, 'L'); // left
            FindPath(row - 1, col, 'U'); // up
            FindPath(row, col + 1, 'R'); // right
            FindPath(row + 1, col, 'D'); // down

            // Mark back the current cell as free
            lab[row, col] = ' ';
        }

        // Remove the last direction from the path
        position--;
    }

    static void PrintPath(char[] path, int startPos, int endPos)
    {
        Console.Write("Found path to the exit: ");
        for (int pos = startPos; pos <= endPos; pos++)
        {
            Console.Write(path[pos]);
        }
        Console.WriteLine();
    }

    static void Main()
    {
        FindPath(0, 0, 'S');
            for(int i = 0; i < path.Length; i++){
        Console.Write(path[i]);
        }
    }
}

结果：

Found path to the exit: RRDDLLDDRRRRRR
Found path to the exit: RRDDRRUURRDDDD
Found path to the exit: RRDDRRRRDD

虽然我可以理解递归是如何在迷宫中运作的，但我无法理解为什么“path []”能够在程序不休息或从离开前一个路线的位置开始的情况下打印出每条路径的单独方向数组。

基本上，我的理解是每个递归都使用相同的全局变量（path []），为什么每个递归不会覆盖方向，而且我们如何能够始终从path [1]开始打印完美的方向？

换句话说，为什么最后path []不是这样的："RRDDLLDDRRRRRRRRDDRRUURRDDDDRRDDRRRRDD？

- JessicaMendoza

也许你可以在代码中设置断点以更好地理解它。 - TheGeneral

1

这是因为在从FindPath返回之前进行了递减。它将始终使position保持在0和lab.GetLength(0) * lab.GetLength(1)之间。 - MarcinJuraszek

@MarcinJuraszek 是正确的。一旦找到出口或搜索超出边界，位置就会回滚到先前的决策点。 - Jonathon Chase

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Polad Samadzada · Accepted Answer

在进行这些递归调用之前，您的位置为1。您可以将堆栈想象成：

Main()->FindPath()

假设为了找到出口，程序进行了3次递归调用。那么堆栈如下所示：

Main()->FindPath()->FindPath()->FindPath()->FindPath()

此时，位置=4。

打印结果后，方法调用返回，但在此之前，它们会将位置减1。

因此，在进行另一组递归调用之前，您的堆栈再次如下：

Main()->FindPath()

而位置=1。