wywwzjj's Blog.

POJ 3984 迷宫问题[BFS]

字数统计: 723阅读时长: 3 min
2018/10/28 Share

定义一个二维数组:

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

此题题意比较简单,就是找一条左上到右下的最短路,并打印出来。这种简单的最短路直接 $BFS$ 就解决了。稍微麻烦一点在于打印,那么该如何去储存这条最短路线呢?题目明确指出打印出坐标,那直接用个 $pair$ 储存一下 $x,\ y$ 就好了,可以尝试建立一个 $pair$ 数组,又需要路线,那我们存一下前驱坐标就行了。问题来了,从哪端开始存方便一些,如果从起始坐标 $(0,\ 0)$ 处就存的话,结点必然不唯一,比如说离 $(0, \ 0)$ 距离为 $1$ 的可能就好几个(ps:此处不理解的话可以去看看 floodfill)。所以尝试一下从结尾处开始存,结尾处的结点前驱就唯一了,想一想为什么?然而从结尾开始存的话又需要一个栈倒一下顺序,那直接从 $(4,\ 4)$ 向 $(0,\ 0)$搜索就好了。

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
#include <cstdio>
#include <queue>
#include <iostream>
using namespace std;
#define mp make_pair
#define fi first
#define se second
#define sf scanf
#define pf printf
#define rep(i,a,b) for(int i=a;i<(b);++i)

bool mm[6][6];
pair<int,int> pre[5][5];

void bfs(int x, int y) {
queue<pair<int, int> > qq; qq.push(mp(x, y));
while(!qq.empty()) {
int inext[] = {0, 0, -1, 1};
int jnext[] = {-1, 1, 0, 0};
rep(k, 0, 4) { // 结点的上下左右各查找一次
int icur = qq.front().fi + inext[k];
int jcur = qq.front().se + jnext[k];
if(icur < 0 || icur >4 || jcur < 0 || // 去除越界位置
jcur > 4 || (icur == x && jcur == y)) continue;
if(!mm[icur][jcur] && !pre[icur][jcur].first) { // 能走并且未走过(pair元素默认为空)
qq.push(mp(icur, jcur)); // 加入队列
// 此时的队首元素即为下一个结点的前驱,不熟悉的朋友可以建立如下结构,熟悉一下BFS,打印出来观察一下
// fg[icur][jcur] = fg[qq.front().first][qq.front().second] + 1;
// fg[i][j]:i, j位置离起点的最短距离
pre[icur][jcur] = qq.front(); // 记录前驱位置
}
if(icur == 0 && jcur == 0) return; // 到终点了就退出
}
qq.pop(); // 查找过的结点就直接pop
}
}

int main() {
//freopen("D:\\i.txt","r",stdin);
rep(i, 0, 5) rep(j, 0, 5) cin>>mm[i][j];

bfs(4, 4);

puts("(0, 0)");
pair<int, int> tmp(0, 0);
while(tmp.fi != 4 || tmp.se != 4) {
int i = tmp.fi;
int j = tmp.se;
pf("(%d, %d)\n", pre[i][j].fi, pre[i][j].se);
tmp = pre[i][j];
}
return 0;
}
CATALOG