题解 | 迷宫问题

#include <bits/stdc++.h>
using namespace std;
struct Point {
    int x, y;
    Point(int x_, int y_): x(x_), y(y_) {}
};

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>>arr(n, vector<int>(m));
    vector<vector<bool>>vis(n, vector<bool>(m, false));
    vector<vector<Point>>pre(n, vector<Point>(m, Point(-1, -1)));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> arr[i][j];
        }
    }
    queue<Point>q;
    q.push(Point(0, 0));
    vis[0][0] = true;
    int di[4] = {-1, 0, 1, 0};
    int dj[4] = {0, 1, 0, -1};
    while (!q.empty()) {
        Point cur = q.front();
        q.pop();
        int it1 = cur.x;
        int it2 = cur.y;

        if (it1 == n - 1 && it2 == m - 1) {
            break;
        }
        for (int i = 0; i < 4; i++) {
            int ni = it1 + di[i];
            int nj = it2 + dj[i];
            if (ni >= 0 && ni < n && nj >= 0 && nj < m && !vis[ni][nj] &&
                    arr[ni][nj] == 0) {
                vis[ni][nj] = true;
                pre[ni][nj] = cur;
                q.push(Point(ni, nj));
            }
        }
    }
    stack<Point>path;
    Point cur(n - 1, m - 1);
    while (cur.x != -1 && cur.y != -1) {
        path.push(cur);
        cur = pre[cur.x][cur.y];
    }
    while (!path.empty()) {
        Point cur = path.top();
        cout << "(" << cur.x << "," << cur.y << ")" << endl;
        path.pop();
    }
    return 0;
}
//广度优先搜索+回溯
//bool数组标记，pre数组保存前驱结点，queue实现广度优先搜索，stack实现回溯
// 64 位输出请用 printf("%lld")