迷宫问题 (POJ - 3984)
题面
定义一个二维数组：
1int maze[5][5] = { 2 0, 1, 0, 0, 0, 3 0, 1, 0, 1, 0, 4 0, 0, 0, 0, 0, 5 0, 1, 1, 1, 0, 6 0, 0, 0, 1, 0, 7};它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。
输入
一个5 × 5的二维数组，表示一个迷宫。数据保证有唯一解。
输出
左上角到右下角的最短路径，格式如样例所示。
样例输入
10 1 0 0 0
20 1 0 1 0
30 0 0 0 0
40 1 1 1 0
50 0 0 1 0
样例输出
1(0, 0)
2(1, 0)
3(2, 0)
4(2, 1)
5(2, 2)
6(2, 3)
7(2, 4)
8(3, 4)
9(4, 4)
提示
无
思路
bfs+路径输出，记录路径有多种方式。
代码
1using namespace std;
2typedef long long ll;
3const int inf = 0x3f3f3f3f;
4const int N = 1e1+5;
5
6int b[N][N] = {{0}};
7bool vis[N][N] = {{0}};
8int n, m;
9
10int dx[] = { 0, 1, -1, 0, 0};
11int dy[] = { 0, 0, 0, 1, -1};
12
13struct P {
14 int x, y;
15 int p[N];
16 int step;
17};
18
19P bfs() {
20 memset(vis, 0, sizeof(vis));
21
22 P sp;
23 sp.x = 0;
24 sp.y = 0;
25 sp.step = 0;
26 memset(sp.p, 0, sizeof(sp.p));
27
28 queue<P> q;
29 q.push(sp);
30 vis[sp.x][sp.y] = 1;
31
32 while(!q.empty()) {
33 P tp = q.front();
34 q.pop();
35
36 if(tp.x==n-1 && tp.y==m-1) {
37 return tp;
38 }
39
40 P np = tp;
41 for(int i=1; i<=4; i++) {
42 int x = np.x = tp.x+dx[i];
43 int y = np.y = tp.y+dy[i];
44
45 if(!vis[x][y] && b[x][y]==0) {
46 np.step = tp.step+1;
47 np.p[np.step] = i;
48 q.push(np);
49 vis[x][y] = 1;
50 }
51 }
52 }
53 return sp;
54}
55
56int main(void) {
57 n = m = 5;
58 for(int i=0; i<n; i++) {
59 for(int j=0; j<m; j++) {
60 scanf("%d", &b[i][j]);
61 }
62 }
63 P ans = bfs();
64 if(ans.step) {
65 int x=0, y=0;
66 for(int i=0; i<=ans.step; i++) {
67 printf("(%d, %d)\n", x+=dx[ans.p[i]], y+=dy[ans.p[i]]);
68 }
69 }
70
71 return 0;
72}