K - 迷宫问题 POJ - 3984（BFS，记录路径）

本文主要是介绍K - 迷宫问题 POJ - 3984（BFS，记录路径），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

定义一个二维数组：

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,

};

它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。
Input
一个5 × 5的二维数组，表示一个迷宫。数据保证有唯一解。
Output
左上角到右下角的最短路径，格式如样例所示。
Sample Input
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
Sample Output
(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4)

思路：如果是迷宫算最短距离，直接每次出队列的时候dis[nex] = dis[now] + 1;即可。但题目要求输出路径，那么我们可以开一个pre[N][N数组记录每一个点的前驱结点（以前考虑过遍历方向的时候把合理的结果进队列最后把队列作为答案即可，但其实这样的结果会考虑到一些非答案的节点）。
注意：POJ的G++有诡异BUG。。。具体看代码区别
PS：3月蓝桥考了这题，大笑之，然后毫无疑问的错了（字典序好像搞错了），重视基础，才有进步啊。

AC代码：

//这题tm的BUG找了我好久，结果是变量定义的位置导致的问题，变量定义在结构体下面就会崩溃，定义在上面就对。。。
//真相原来是编译器的问题，G++RE，C++AC。。。
#include <cstdio>
#include <queue>
#include <stack>
#include <cstring>using namespace std;int dirx[] = {1,-1,0,0};
int diry[] = {0,0,-1,1};
int maze[10][10];
int vis[10][10];
struct node
{int x,y;node(int x,int y):x(x),y(y){}node(){}
}pre[10][10];int check(int x,int y)
{if(x < 0 || y < 0 || x >= 5 || y >= 5)return 1;if(vis[x][y] == 1)return 1;if(maze[x][y] == 1)return 1;return 0;
}void bfs()
{queue<node>Q;Q.push(node(0,0));memset(vis,0,sizeof(vis));vis[0][0] = 1;while(!Q.empty()){node now = Q.front();Q.pop();for(int i = 0;i < 4;i++){int tx = now.x + dirx[i];int ty = now.y + diry[i];if(tx>=0&&ty<5&&tx>=0&&ty<5&&vis[tx][ty]==0&&maze[tx][ty]==0){vis[tx][ty]=1;Q.push(node(tx,ty));pre[tx][ty]=node(now.x,now.y);if(tx==4&&ty==4) return ;}}}
}int main()
{for(int i = 0;i <= 4;i++){for(int j = 0;j <= 4;j++){scanf("%d",&maze[i][j]);}}bfs();int tx = 4,ty = 4;stack<node>S;while(true){S.push(node(tx,ty));if(tx == 0 && ty == 0)break;int x = tx,y = ty;tx = pre[x][y].x;ty = pre[x][y].y;}while(!S.empty()){node now = S.top();S.pop();printf("(%d, %d)\n",now.x,now.y);}return 0;
}```wa掉的代码：
```cpp
这题tm的BUG找了我好久，结果是变量定义的位置导致的问题，变量定义在结构体下面就会崩溃，定义在上面就对。。。
#include <cstdio>
#include <queue>
#include <stack>
#include <cstring>using namespace std;struct node
{int x,y;node(int x,int y):x(x),y(y){}node(){}
}pre[10][10];int dirx[] = {1,-1,0,0};
int diry[] = {0,0,-1,1};
int maze[10][10];
int vis[10][10];int check(int x,int y)
{if(x < 0 || y < 0 || x >= 5 || y >= 5)return 1;if(vis[x][y] == 1)return 1;if(maze[x][y] == 1)return 1;return 0;
}void bfs()
{queue<node>Q;Q.push(node(0,0));memset(vis,0,sizeof(vis));vis[0][0] = 1;while(!Q.empty()){node now = Q.front();Q.pop();for(int i = 0;i < 4;i++){int tx = now.x + dirx[i];int ty = now.y + diry[i];if(tx>=0&&ty<5&&tx>=0&&ty<5&&vis[tx][ty]==0&&maze[tx][ty]==0){vis[tx][ty]=1;Q.push(node(tx,ty));pre[tx][ty]=node(now.x,now.y);if(tx==4&&ty==4) return ;}}}
}int main()
{for(int i = 0;i <= 4;i++){for(int j = 0;j <= 4;j++){scanf("%d",&maze[i][j]);}}bfs();int tx = 4,ty = 4;stack<node>S;while(true){S.push(node(tx,ty));if(tx == 0 && ty == 0)break;int x = tx,y = ty;tx = pre[x][y].x;ty = pre[x][y].y;}while(!S.empty()){node now = S.top();S.pop();printf("(%d, %d)\n",now.x,now.y);}return 0;
}