c++ 递归 迷宫全路径问题

Question

题目是探索迷宫的所有路径。
疑问：为什么第一个图的判定就是对的，第二个图的就不对，少了4组解呢？

Answer 1

答案引用自chatgpt生成，望对题主有所帮助/启发；若有帮助，还望采纳！

在C++中，我们可以使用深度优先搜索（DFS）算法来解决迷宫全路径问题。这个问题可以看作是在一个二维网格中，从起点到终点的所有可能路径的搜索问题。

首先，我们需要定义一个二维数组来表示迷宫，其中0表示可以通过的路径，1表示墙壁或者障碍物。然后，我们需要定义一个同样大小的二维数组来记录我们的路径。

接下来，我们从起点开始，每次尝试向上、下、左、右四个方向移动，如果某个方向是可行的（即没有越界，且该位置是0），我们就向该方向移动一步，并标记该位置为已访问（例如将其值设为2）。然后，我们递归地对新的位置进行同样的操作。如果新的位置是终点，那么我们就找到了一条路径。如果新的位置不能继续前进，那么我们就回溯到上一个位置，尝试其他的方向。

以下是一个简单的C++代码示例：

#include <iostream>
#include <vector>
using namespace std;

void dfs(vector<vector<int>>& maze, vector<vector<int>>& path, int x, int y) {
    int rows = maze.size();
    int cols = maze[0].size();
    if (x < 0 || x >= rows || y < 0 || y >= cols || maze[x][y] != 0) {
        return;
    }
    if (path[x][y] == 1) {
        return;
    }
    path[x][y] = 1;
    if (x == rows - 1 && y == cols - 1) {
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                cout << path[i][j] << " ";
            }
            cout << endl;
        }
        cout << endl;
    } else {
        dfs(maze, path, x - 1, y);
        dfs(maze, path, x + 1, y);
        dfs(maze, path, x, y - 1);
        dfs(maze, path, x, y + 1);
    }
    path[x][y] = 0;
}

int main() {
    vector<vector<int>> maze = {{0, 0, 0}, {0, 1, 0}, {0, 0, 0}};
    vector<vector<int>> path(maze.size(), vector<int>(maze[0].size(), 0));
    dfs(maze, path, 0, 0);
    return 0;
}

在这个代码中，dfs函数是我们的深度优先搜索函数，它接受迷宫、路径和当前位置作为参数。我们首先检查当前位置是否越界或者是否是墙壁，如果是，则直接返回。然后，我们检查当前位置是否已经访问过，如果是，则直接返回。接着，我们将当前位置标记为已访问，然后尝试向四个方向移动。如果新的位置是终点，我们就打印出当前的路径。否则，我们递归地对新的位置进行同样的操作。最后，我们将当前位置标记为未访问，以便于后续的搜索。