poj 3984 迷宫问题（bfs， 记录路径）

迷宫问题 Time Limit: 1000MS Memory Limit: 65536KTotal Submissions: 16156 Accepted: 9636

Description

定义一个二维数组：  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)

Source

思路：用一个结构体保存该点坐标，同时记录该点的数组下标，和上一步的数组下标，最后从终点开始回溯就能找到路径。

代码：

#include<iostream> #include<cstring> #include<cstdio> #include<queue> #include<stack> using namespace std; const int maxn = 10; int pic[maxn][maxn]; bool book[maxn][maxn]; struct node { int x, y, id, pre; node(int xx, int yy, int ii, int pp): x(xx), y(yy), id(ii), pre(pp) {} node() {} }a[maxn*maxn]; void bfs(void) { int k = 1, next[4][2] = {0, 1, 0, -1, 1, 0, -1, 0}; queue<node> q; q.push(node(0, 0, 1, 0)); a[k++] = node(0, 0, 1, 0); book[0][0] = 1; node t; while(q.size()) { t = q.front(); q.pop(); if(t.x == 4 && t.y == 4) break; for(int i = 0; i < 4; i++) { int tx = t.x+next[i][0]; int ty = t.y+next[i][1]; if(tx >= 0 && ty >= 0 && tx < 5 && ty < 5 && !book[tx][ty] && !pic[tx][ty]) { a[k++] = node(tx, ty, k, t.id); q.push(a[k-1]); book[tx][ty] = 1; } } } stack<node> s; while(1) { s.push(t); if(!t.pre) break; t = a[t.pre]; } while(!s.empty()) printf("(%d, %d)\n", s.top().x, s.top().y), s.pop(); } int main(void) { for(int i = 0; i < 5; i++) for(int j = 0; j < 5; j++) scanf("%d", &pic[i][j]); bfs(); return 0; }