POJ 3984 迷宫问题(bfs+路径记录)

迷宫问题

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<cstdio>
 2 #include<queue>
 3 #include<cstring>
 4 using namespace std;
 5 
 6 struct point
 7 {
 8     int x;
 9     int y;
10 };
11 
12 int d[4][2]={0,1,1,0,0,-1,-1,0};
13 int vis[6][6];
14 int maze[7][7];
15 point rec[5][5],a[26];
16 
17 void bfs(int x,int y)
18 {
19     queue<point>q;
20     point init;
21     init.x=init.y=0;
22     q.push(init);
23     vis[x][y]=1;
24     while(!q.empty())
25     {
26         point t1,t2;
27         t1=q.front();
28         q.pop();
29         if(t1.x==4&&t1.y==4)
30         return;
31         for(int i=0;i<4;i++)
32         {
33             t2.x=t1.x+d[i][0];
34             t2.y=t1.y+d[i][1];
35             if(t2.x>=0&&t2.x<5&&t2.y>=0&&t2.y<5)
36             {
37                 if(!vis[t2.x][t2.y]&&maze[t2.x][t2.y]==0)
38                 {    
39                     rec[t2.x][t2.y].x=t1.x;
40                     rec[t2.x][t2.y].y=t1.y;
41                     q.push(t2);
42                     vis[t2.x][t2.y]=1;
43                 }
44             }
45         }
46     }
47 }
48 
49 int main()
50 {
51     //freopen("in.txt","r",stdin);
52     int i,j;
53     memset(vis,0,sizeof(vis));
54     for(i=0;i<5;i++)
55     for(j=0;j<5;j++)
56     scanf("%d",&maze[i][j]);
57     bfs(0,0);
58     int x=4,y=4,k=0;
59     while(x!=0||y!=0)
60     {
61         a[k].x=x;
62         a[k].y=y;
63         point temp=rec[x][y];
64         x=temp.x;
65         y=temp.y;
66         k++;
67     }
68     a[k].x=a[k].y=0;
69     for(i=k;i>=0;i--)
70     printf("(%d, %d)
",a[i].x,a[i].y);
71     return 0;
72 }