迷宫深度算法查找路径

迷宫深度优先搜索（Maze DFS）通常用于寻找从起点到终点的路径，尤其是在二维网格状迷宫中。这种算法会从起点开始，探索每个可以走的邻居节点，如果找到终点则返回路径，如果没有，则回溯并尝试下一个节点，直到所有可能路径都尝试过。

以下是简单的C++代码实现迷宫深度优先搜索查找路径：

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

bool isSafe(int x, int y, const vector<vector<bool>>& maze) {
    return (x >= 0 && x < maze.size() && y >= 0 && y < maze[0].size() && maze[x][y]);
}

void findPath(vector<vector<bool>>& maze, int srcX, int srcY, int destX, int destY, vector<vector<int>>& path, vector<vector<bool>>& visited) {
    stack<pair<int, int>> s;
    s.push({srcX, srcY});
    visited[srcX][srcY] = true;

    while (!s.empty()) {
        auto [currentX, currentY] = s.top();
        s.pop();

        if (currentX == destX && currentY == destY) {
            printPath(path, currentX, currentY);
            return;
        }

        for (int dx = -1; dx <= 1; dx++) {
            for (int dy = -1; dy <= 1; dy++) {
                if (isSafe(currentX + dx, currentY + dy, maze)) {
                    if (!visited[currentX + dx][currentY + dy]) {
                        s.push({currentX + dx, currentY + dy});
                        visited[currentX + dx][currentY + dy] = true;
                        path[currentX][currentY] = currentX + dx * maze.size() + currentY; // 根据方向编码路径
                    }
                }
            }
        }
    }
}

void printPath(vector<vector<int>>& path, int endX, int endY) {
    cout << "Path found from (" << endX << ", " << endY << ") to destination: ";
    while (path[endX][endY] != 0) {
        int prevX = endX, prevY = endY;
        endX = path[endX][endY] / maze.size(); // 取整数部分得到行
        endY = path[endX][endY] % maze.size(); // 取余数得到列

        cout << "(" << prevX << ", " << prevY << ") -> ";
    }
    cout << "(" << endX << ", " << endY << ")";
}

int main() {
    vector<vector<bool>> maze = {{1, 1, 0, 0}, {0, 1, 0, 1}, {1, 1, 0, 0}, {0, 0, 0, 1}};
    int src = 0, dest = 3;
    findPath(maze, src / maze.size(), src % maze.size(), dest / maze.size(), dest % maze.size(), {}, maze);
    return 0;
}

这个代码首先检查当前位置是否安全，然后将可行的位置压入堆栈，并标记已访问。当找到目标位置时，它会回溯并打印路径。注意，这里的路径存储在一个二维数组`path`中，通过行和列的组合来记录路径的方向。