带屏蔽的网站做水晶头,网站建设zvge,外贸网站建设 福田,网站制作开发教程算法提高之迷宫问题 核心思想#xff1a;最短路问题 从(n-1,n-1)开始bfs 往前走一个就存入pre数组 之后再遍历pre数组输出 #include iostream#include cstring#include algorithmusing namespace std;const int N 1010,M N*N;#define x first#def…算法提高之迷宫问题 核心思想最短路问题 从(n-1,n-1)开始bfs 往前走一个就存入pre数组 之后再遍历pre数组输出 #include iostream#include cstring#include algorithmusing namespace std;const int N 1010,M N*N;#define x first#define y secondtypedef pairint, 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(hhtt){PII t p[hh];int at.x,bt.y;for(int i0;i4;i){int x adx[i],y bdy[i];if(x0||xn||y0||yn||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 x0,y0; //正序输出while(x!n-1 || y!n-1){coutx yendl;auto t pre[x][y];x t.x,y t.y;}coutn-1 n-1endl;}int main(){cinn;for(int i0;in;i)for(int j0;jn;j) cing[i][j];bfs();return 0;}
