acwing 1076 迷宫问题

#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
#include<vector>
 
using namespace std ;
const int N = 1010 ;
int d[4][2] = {{-1,0},{0,1},{1,0},{0,-1}} ;
struct node{
  int x ,  y ;
 
};
queue<node> q;
int n;
int g[N][N] ;
node pre[N][N] ;
int dis[N][N] ;
vector<node> fa ;
void bfs(){
  q.push({0,0}) ;
  dis[0][0] = 0 ;
  while(!q.empty()){
    node now = q.front() ;
    q.pop() ;
    int x = now.x , y = now.y ;
    if(x == n-1 && y == n-1){
      int tmx = x , tmy = y;
      while(tmx != 0||tmy != 0){
        node b = {tmx,tmy} ;
        fa.push_back(b) ;
        node a = pre[tmx][tmy] ;
        tmx = a.x; tmy = a.y ;
      }
      fa.push_back({0,0}) ;
      return ;
    }
    for(int i = 0 ; i < 4 ; i ++){
      int tx = x + d[i][0] , ty = y + d[i][1] ;
      if(tx<0||tx>=n||ty<0||ty>=n||g[tx][ty]||dis[tx][ty]!=-1) continue ;
      q.push({tx,ty}) ;
      dis[tx][ty] = dis[x][y] + 1 ;
      pre[tx][ty] = {x,y} ;
    }
  }
}
int main(){
  cin >> n  ;
  for(int i = 0 ; i < n ;i ++){
    for(int j = 0 ; j < n ; j ++){
      cin >> g[i][j] ;
    }
  }
  memset(dis,-1,sizeof(dis)) ;
  bfs() ;
  for(int i = fa.size()-1 ; i >=0 ; i --){
    cout << fa[i].x << " " << fa[i].y << endl ;
  }
}