【教程】BFS学习笔记

|
  • 例子(已被授予主人公的名字使用权)

ZZJ 进入了一个 n × m 的迷宫矩阵，执着的他表示要穿过迷宫。

ZZJ 在地图的左上角，而迷宫出口在右下角，设进入每个房间都需要 1 的时间，他在入口的地面上捡到一张迷宫地图，发现有一些障碍物（图中以“障碍”表示，代码中以“#”表示，存在map数组中），于是他决定计算出自己到终点最少需要时间（请思考后再往下看）。

\ 1 2 3 4 5 6 7
1 起点
2 障碍
3 障碍
4 障碍
5 障碍 终点
  • 思路：
  • 首先，我们需要一个小本本存ZZJ到达的地方及步数：
1
struct nod{int x,y,t;}f[100001];//x,y表示位置，t表示ZZJ到达此点需要的步数

  • 其次，我们需要一个bool数组存i,j这个位置是否被走过以及一个map数组存地图：

    1
    bool bz[101][101];//这里以0<n,m<=100为数据范围，实际情况请以题面修改数组范围
    2
    char map[101][101];

  • 再次，我们需要一个方向数组，使ZZJ能上、下、左、右移动：

1
int dx[4]={0,1,0,-1};
2
int dy[4]={1,0,-1,0};
  • 准备完毕了，ZZJ可以出发啦!
  • 首先，ZZJ将自己的位置存进小本本的第一格里：
1
tou=1,wei=2;//用两个指针指向小本本队头和队尾
2
f[tou].x=1;
3
f[tou].y=1;
4
f[tou].t=0;
  • 接着，ZZJ通过方向数组到达一个新位置：
1
int nx=f[tou].x+dx[i];
2
int ny=f[tou].y+dy[i];
  • 但是ZZJ有可能跑出了迷宫，掉下悬崖了，所以我们要判断一下ZZJ站在的位置是否在迷宫内：
1
if(nx<1||nx>n||ny<1||ny>m)continue;//跑出去就不要他了

  • 如果ZZJ已经到了终点，那就是最短到达的距离啦（因为在这个地图中到达每一个点距离都为1），输出小本本的当前的 t+1 ，退出搜索就好啦就好啦：

    1
    if(nx==n&&ny==m) 
    2
    {
    3
    printf("ZZJ到达终点的最短距离是：%d",f[tou].t+1);
    4
    return;
    5
    }

  • 如果ZZJ到达的是一个新的非障碍的点，并且没来过，ZZJ就在他的小本本上记录下他的位置：

1
if(map[nx][ny]=='.'&&bz[nx][ny]==false)
2
{
3
    bz[nx][ny]=true;
4
    f[wei].x=nx;
5
    f[wei].y=ny;
6
    f[wei].t=f[tou].t+1;
7
    wei++;
8
}
  • ZZJ走过了（遍历）周围可走的点后，就将小本本的队头往后挪一个，开始了新的遍历（直到没有点可以更新出新的点时停止，即 $tou=wei$ ）：
1
tou++;
  • 这就是整个bfs的完整过程啦，上完整代码：
1
#include<cstdio>
2
int n,m,tou,wei;
3
int dx[4]={0,1,0,-1};
4
int dy[4]={1,0,-1,0};
5
bool bz[101][101];
6
char map[101][102];
7
struct nod{int x,y,t;} f[10001];
8
void bfs(int sx,int sy)
9
{
10
    tou=1,wei=2;
11
    f[tou].x=sx;
12
    f[tou].y=sy;
13
    f[tou].t=0;
14
    while(tou<wei)
15
    {
16
        for(int i=0;i<3;i++)
17
        {
18
            int nx=f[tou].x+dx[i];
19
            int ny=f[tou].y+dy[i];
20
            if(nx<1 || nx>n || ny<1 || ny>m)
21
                continue;
22
            if(nx==n && ny==m)
23
            {
24
                printf("ZZJ到达终点的最短距离是：%d",f[tou].t+1);
25
                return;
26
            }
27
            if(map[nx][ny]=='.'&&bz[nx][ny]==false)
28
            {
29
                bz[nx][ny]=true;
30
                f[wei].x=nx;
31
                f[wei].y=ny;
32
                f[wei].t=f[tou].t+1;
33
                wei++;
34
            }
35
        }
36
        tou++;
37
    }
38
}
39
int main()
40
{
41
    scanf("%d%d",&n,&m);
42
    for(int i=1;i<=n;i++)
43
    {
44
        for(int j=1;j<=m+1;j++)
45
        {
46
            scanf("%c",&map[i][j]);//结尾要多读一个换行符
47
        }
48
    }
49
    bfs(1,1);
50
    return 0;
51
}
  • 如果理解透了这道题，就练练手吧：
  • 题目练习
  • 鸣谢： @$\text{zhongzijun}$ 。