c++ bfs最短路径记录

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> PII;
#define fi first
#define se second

const int N=1005;
int G[N][N];
const int dirs[4][2]={{-1,  0}, {0, 1}, {1, 0}, {0, -1}};
int n;
PII pre[N][N];
stack<PII> st;

int main(){
    memset(pre, -1, sizeof pre);
    memset(G, 0x00, sizeof G);
    cin>>n;
    for(int i=0; i<n; ++i)
        for(int j=0; j<n; ++j)
            cin>>G[i][j];

    queue<PII> q;
    q.push({0, 0});
    pre[0][0]={0, 0};
    while(!q.empty()){
        int x=q.front().fi;
        int y=q.front().se;
        q.pop();
        for(int i=0; i<4; ++i){
            int nx=x+dirs[i][0];
            int ny=y+dirs[i][1];
            if(0<=nx && nx<n && 0<=ny && ny<n && pre[nx][ny].fi==-1 && !G[nx][ny]){
                pre[nx][ny]={x, y};
                q.push({nx, ny});
                if(nx==n-1 && ny==n-1) break;
            }
        }
    }

    PII path = {n-1, n-1};
    while(1){
        st.push(path);
        if(path.fi==0 && path.se==0) break;
        path=pre[path.fi][path.se];
    }

    while(!st.empty()){
        cout<<st.top().fi<<" "<<st.top().se<<endl;
        st.pop();
    }

    return 0;
}