AcWing1076. 迷宫问题 宽搜

int maze[5][5] = {

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,

};

5
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

0 0
1 0
2 0
2 1
2 2
2 3
2 4
3 4
4 4

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
#define x first
#define y second
typedef pair<int,int> pii;
int n,g[N][N];
pii pre[N][N];
void bfs(int x,int y){
    queue<pii>q;
    int nx[4]={-1,1,0,0},ny[4]={0,0,1,-1};
    q.push({x,y});
    memset(pre,-1,sizeof pre);
    pre[x][y]={x,y};
    while(!q.empty()){
        auto now=q.front();
        q.pop();
        for(int i=0;i<4;i++){
            int a=now.x+nx[i],b=now.y+ny[i];
            if(a<0||b<0||a>n-1||b>n-1)continue;
            if(g[a][b])continue;
            if(pre[a][b].x!=-1)continue;
            q.push({a,b});
            pre[a][b]=now;
        }
    }
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++)cin>>g[i][j];
    }
    bfs(n-1,n-1);
    pii tep(0,0);
    while(1){
        cout<<tep.x<<" "<<tep.y<<endl;
        tep=pre[tep.x][tep.y];
        if(tep.x==n-1&&tep.y==n-1)break;
    }
    cout<<tep.x<<' '<<tep.y<<endl;
    return 0;
    
}