算法提高之迷宫问题

核心思想：最短路问题
- 从(n-1,n-1)开始bfs 往前走一个就存入pre数组之后再遍历pre数组输出

  #include <iostream>
  #include <cstring>
  #include <algorithm>
  
  using namespace std;
  const int N = 1010,M =N*N;
  #define x first
  #define y second
  typedef pair<int, int> PII;
  
  int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
  PII pre[N][N];
  int g[N][N];
  int n;
  bool st[N][N];
  int hh,tt=-1;
  PII p[M];
  void bfs()
  {
      st[n-1][n-1] = true;
      p[++tt] = {n-1,n-1};  //从n-1,n-1开始
      
      while(hh<=tt)
      {
          PII t = p[hh++];
          int a=t.x,b=t.y;
          for(int i=0;i<4;i++)
          {
              int x = a+dx[i],y = b+dy[i];
              if(x<0||x>=n||y<0||y>=n||g[x][y]||st[x][y]) continue;
              st[x][y] = true;
              p[++tt] = {x,y};
              pre[x][y] = t;  //x,y前驱为t(实际是后驱吧 t -> (x,y))
          }
      }
      
      int x=0,y=0;  //正序输出
      while(x!=n-1 || y!=n-1)
      {
          cout<<x<<" "<<y<<endl;
          auto t = pre[x][y];
          x = t.x,y = t.y;
      }
      cout<<n-1<<" "<<n-1<<endl;
  }
  int main()
  {
      cin>>n;
      for(int i=0;i<n;i++)
          for(int j=0;j<n;j++)    
              cin>>g[i][j];
              
      bfs();
      return 0;
  }