迷宫问题

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 24661		Accepted: 14402

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)
bfs遍历然后记录下所走过的路.

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 #include <algorithm>
 5 #include <queue>
 6 #include <stack>
 7 #define N 105
 8 #define inf 1000000000
 9 using namespace std;
10 int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
11 typedef pair<int,int> P;
12 queue<P> q;
13 stack<P> s;
14 P fa[5][5];
15 int k[5][5];
16 int vis[5][5];
17 int bfs(){
18   for(int i=0;i<5;i++)
19     for(int j=0;j<5;j++)
20       vis[i][j]=inf;
21   q.push(P(0,0));
22   vis[0][0]=1;
23   while(q.size()){
24     P r=q.front();q.pop();
25     if(r.first==4&&r.second==4){
26       break;
27     }
28     for(int i=0;i<4;i++){
29       int xx=r.first+dir[i][0];
30       int yy=r.second+dir[i][1];
31       if(xx>=0&&xx<=4&&yy>=0&&yy<=4&&k[xx][yy]==0&&vis[xx][yy]==inf){
32         q.push(P(xx,yy));
33         vis[xx][yy]=1;
34         fa[xx][yy]=r;
35     }
36   }
37  }
38 }
39 
40 int main(){
41   for(int i=0;i<5;i++)
42     for(int j=0;j<5;j++)
43       cin>>k[i][j];
44   bfs();
45   int x,y;
46   x=y=4;
47   s.push(P(4,4));
48   while(x!=0||y!=0){
49     P p=fa[x][y];
50     s.push(p);
51     x=p.first;
52     y=p.second;
53   }
54   while(s.size()){
55     P p=s.top();
56     s.pop();
57     cout<<"("<<p.first<<", "<<p.second<<")"<<endl;;
58   }
59   return 0;
60 }