算法提高之迷宫问题

算法提高之迷宫问题

• 核心思想：最短路问题

  • 从(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 secondtypedef 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;}