此题让输出路径 用数组pre[i][j] = num 表示num -> (i,j) (num是一个pair) 要逆序打印输出(可以用个栈） 或者开始是从终点找起点

BFS

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

typedef pair<int,int> PII;
const int N = 1001;
int n;

int m[N][N];
PII path[N][N];

const int dx[] = {-1,1,0,0}, dy[] = {0,0,-1,1};

void bfs() {
    queue<PII> q;
    q.push(make_pair(n - 1,n - 1));
    m[n - 1][n - 1] = 1;
    while (q.size()) {
        auto cur = q.front(); q.pop();
        for (int i = 0; i < 4; i ++ ) {
            int nx = cur.first + dx[i], ny = cur.second + dy[i];
            if (nx < 0 || ny < 0 || nx >= n || ny >= n || m[nx][ny] == 1) continue;
            path[nx][ny] = cur;
            q.push(make_pair(nx,ny));
            m[nx][ny] = 1;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for (int i = 0; i < n; i ++ ) 
        for (int j = 0; j < n; j ++ ) 
            cin >> m[i][j];

    bfs();
    int i = 0, j = 0;
    while (i != n - 1 || j != n - 1) {
        cout << i << ' ' << j << endl;
        int x, y;
        x = path[i][j].first;
        y = path[i][j].second;
        i = x;
        j = y;
    }
    cout << n - 1 << ' ' << n - 1 << endl;
    return 0;
}

作者：acking101

别的同学的题解：正序+逆序