思路

为了记录bfs的路径，使用额外的二维数组（每个元素是一个pair）记录当前位置的下一个位置。反方向bfs（从右下到左上）可完成路径的记录。

C++ 代码

#include <iostream>
#include <queue>

using namespace std;

const int N = 1010;

int g[N][N], v[N][N], n;
queue<pair<int, int> > q;
pair<int, int> mem[N][N];

void bfs(){
    int dx[4] = {0, 0, 1, -1}, dy[4] = {-1, 1, 0, 0};
    q.push({n-1, n-1});
    v[n-1][n-1] = 1;
    while(!q.empty()){
        auto t = q.front();
        q.pop();
        if(t.first == 0 && t.second == 0) return;
        for(int i=0; i<4; i++){
            int x = t.first + dx[i], y = t.second + dy[i];
            if(x>=0 && x < n && y>=0 && y < n && g[x][y] == 0 && v[x][y] == 0){
                q.push({x, y});
                v[x][y] = 1;
                mem[x][y] = {t.first, t.second};
            }
        }
    }
    return;    
}

int main(){
    cin >> n;
    for(int i=0; i<n; i++)
        for(int j=0; j< n; j++)
            cin >> g[i][j];

    bfs();

    int x = 0, y = 0;
    while(x < n -1 || y < n - 1){
        cout << x << " " << y << endl;
        int tx = x, ty = y;
        x = mem[tx][ty].first;
        y = mem[tx][ty].second;
    }
    cout << x << " " << y << endl;
}