【题解】POJ-3984 迷宫问题

迷宫问题 (POJ - 3984)

题面

定义一个二维数组:

1
2
3
4
5
6
7
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表示可以走的路,只能横着走或竖着走,不能斜着走,要求编程序找出从左上角到右下角的最短路线。

输入

一个5 × 5的二维数组,表示一个迷宫。数据保证有唯一解。

输出

左上角到右下角的最短路径,格式如样例所示。

样例输入

1
2
3
4
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
2
3
4
5
6
7
8
9
(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4)

提示

思路

bfs+路径输出,记录路径有多种方式。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int N = 1e1+5;

int b[N][N] = {{0}};
bool vis[N][N] = {{0}};
int n, m;

int dx[] = { 0, 1, -1, 0, 0};
int dy[] = { 0, 0, 0, 1, -1};

struct P {
int x, y;
int p[N];
int step;
};

P bfs() {
memset(vis, 0, sizeof(vis));

P sp;
sp.x = 0;
sp.y = 0;
sp.step = 0;
memset(sp.p, 0, sizeof(sp.p));

queue<P> q;
q.push(sp);
vis[sp.x][sp.y] = 1;

while(!q.empty()) {
P tp = q.front();
q.pop();

if(tp.x==n-1 && tp.y==m-1) {
return tp;
}

P np = tp;
for(int i=1; i<=4; i++) {
int x = np.x = tp.x+dx[i];
int y = np.y = tp.y+dy[i];

if(!vis[x][y] && b[x][y]==0) {
np.step = tp.step+1;
np.p[np.step] = i;
q.push(np);
vis[x][y] = 1;
}
}
}
return sp;
}

int main(void) {
n = m = 5;
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) {
scanf("%d", &b[i][j]);
}
}
P ans = bfs();
if(ans.step) {
int x=0, y=0;
for(int i=0; i<=ans.step; i++) {
printf("(%d, %d)\n", x+=dx[ans.p[i]], y+=dy[ans.p[i]]);
}
}

return 0;
}