C++ 迷宫求解算法：非递归栈实现，寻找所有路径和最短路径

#include #include #include using namespace std;

struct Node { int x; int y; Node(int i, int j) : x(i), y(j) {}
};

bool isValid(int x, int y, int m, int n, vector<vector>& maze) { if (x < 0 || x >= m || y < 0 || y >= n || maze[x][y] == 1) { return false; } return true; }

void findPath(int m, int n, vector<vector>& maze) { int startX = 0; int startY = 0; int endX = m - 1; int endY = n - 1;

stack<Node> s;
s.push(Node(startX, startY));
maze[startX][startY] = 1; // 标记已访问过的点

while (!s.empty()) {
    Node curr = s.top();
    int x = curr.x;
    int y = curr.y;

    if (x == endX && y == endY) {
        cout << '(' << x << ',' << y << ')'; // 输出最终路径
        return;
    }

    bool found = false;
    // 向下走
    if (isValid(x + 1, y, m, n, maze)) {
        s.push(Node(x + 1, y));
        maze[x + 1][y] = 1;
        found = true;
    }
    // 向右走
    else if (isValid(x, y + 1, m, n, maze)) {
        s.push(Node(x, y + 1));
        maze[x][y + 1] = 1;
        found = true;
    }
    // 向上走
    else if (isValid(x - 1, y, m, n, maze)) {
        s.push(Node(x - 1, y));
        maze[x - 1][y] = 1;
        found = true;
    }
    // 向左走
    else if (isValid(x, y - 1, m, n, maze)) {
        s.push(Node(x, y - 1));
        maze[x][y - 1] = 1;
        found = true;
    }

    if (!found) {
        // 说明当前节点无法继续向下探索
        s.pop();
    }
}

cout << "No path found." << endl;

}

int main() { int m = 5; int n = 5; vector<vector> maze = { {0, 1, 0, 0, 0}, {0, 1, 0, 1, 0}, {0, 0, 0, 0, 0}, {0, 1, 1, 1, 0}, {0, 0, 0, 1, 0} };

findPath(m, n, maze);

return 0;

}