poj 3984 迷宫问题

迷宫问题

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 16238		Accepted: 9692

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

Sample Output

(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4)

不说了，一切尽在代码中（遍历到的每个节点保存到达它的前一个节点信息）

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <queue>
 5 using namespace std;
 6 typedef struct node{
 7     int x, y;
 8     struct node *pre;
 9 } Node;
10 int a[5][5];
11 int visit[5][5];
12 
13 int dir_dx[4] = {-1, 0, 1, 0};//方向数组
14 int dir_dy[4] = {0, 1, 0, -1};
15 
16 void path(Node *p){//递归输出结果
17     if(p == NULL)
18         return;
19     //if(p.x == 0 && p.y == 0)
20     //    printf("(%d, %d)
", p.x, p.y);
21     path(p->pre);
22     printf("(%d, %d)
", p->x, p->y);
23 
24 }
25 
26 int main(){
27     int i, j, start = 0, w = 1, dx, dy;
28     for(i = 0; i < 5; i++)
29         for(j = 0; j < 5; j++)
30             cin >> a[i][j];
31     Node que[1000], temp;
32     Node st;//初始状态节点
33     st.x = 0;
34     st.y = 0;
35     st.pre = NULL;
36     que[start] = st;
37     visit[0][0] = 1;
38     while(!(que[start].x == 4 && que[start].y == 4)){
39         temp = que[start];
40         for(i = 0; i < 4; i++){
41             dx = temp.x + dir_dx[i];
42             dy = temp.y + dir_dy[i];
43             if(dx >= 0 && dx < 5 && dy >= 0 && dy < 5 && a[dx][dy] == 0 && visit[dx][dy] == 0){
44                 visit[dx][dy] = 1;
45                 Node t;
46                 t.x = dx; t.y = dy; 
47                 t.pre = &que[start];//如果t.pre = &temp,则出错 
48                 que[w++] = t;
49             }
50         }
51         start++;
52     }
53     path(&que[start]);
54     return 0;
55 }