【教程】BFS学习笔记

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

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

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

| \\ | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|------|---|---|---|---|---|---|---|
| 1 | 起点 |  |  |  |  |  |  |
| 2 |  |  |  |  | 障碍 |  |  |
| 3 |  |  | 障碍 |  |  |  |  |
| 4 |  |  |  |  | 障碍 |  |  |
| 5 |  | 障碍 |  |  |  |  | 终点 |

<!--more-->

- 思路:
- 首先,我们需要一个小本本存ZZJ到达的地方及步数:

```
struct nod{int x,y,t;}f[100001];//x,y表示位置,t表示ZZJ到达此点需要的步数
```

- 其次,我们需要一个bool数组存i,j这个位置是否被走过以及一个map数组存地图:
  
   ```
   bool bz[101][101];//这里以0<n,m<=100为数据范围,实际情况请以题面修改数组范围
   char map[101][101];
   ```
- 再次,我们需要一个方向数组,使ZZJ能上、下、左、右移动:

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

- 准备完毕了,ZZJ可以出发啦!
- 首先,ZZJ将自己的位置存进小本本的第一格里:

```
tou=1,wei=2;//用两个指针指向小本本队头和队尾
f[tou].x=1;
f[tou].y=1;
f[tou].t=0;
```

- 接着,ZZJ通过方向数组到达一个新位置:

```
int nx=f[tou].x+dx[i];
int ny=f[tou].y+dy[i];
```

- 但是ZZJ有可能跑出了迷宫,掉下悬崖了,所以我们要判断一下ZZJ站在的位置是否在迷宫内:

```
if(nx<1||nx>n||ny<1||ny>m)continue;//跑出去就不要他了
```

- 如果ZZJ已经到了终点,那就是最短到达的距离啦(因为在这个地图中到达每一个点距离都为1),输出小本本的当前的 `t+1` ,退出搜索就好啦就好啦:
  
   ```
   if(nx==n&&ny==m)
   {
   printf("ZZJ到达终点的最短距离是:%d",f[tou].t+1);
   return;
   }
   ```
- 如果ZZJ到达的是一个新的非障碍的点,并且没来过,ZZJ就在他的小本本上记录下他的位置:

```
if(map[nx][ny]=='.'&&bz[nx][ny]==false)
{
     bz[nx][ny]=true;
     f[wei].x=nx;
     f[wei].y=ny;
     f[wei].t=f[tou].t+1;
     wei++;
}
```

- ZZJ走过了(遍历)周围可走的点后,就将小本本的队头往后挪一个,开始了新的遍历(直到没有点可以更新出新的点时停止,即 $tou=wei$ ):

```
tou++;
```

- 这就是整个bfs的完整过程啦,上完整代码:

```
#include<cstdio>
int n,m,tou,wei;
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
bool bz[101][101];
char map[101][102];
struct nod{int x,y,t;} f[10001];
void bfs(int sx,int sy)
{
     tou=1,wei=2;
     f[tou].x=sx;
     f[tou].y=sy;
     f[tou].t=0;
     while(tou<wei)
     {
         for(int i=0;i<3;i++)
         {
             int nx=f[tou].x+dx[i];
             int ny=f[tou].y+dy[i];
             if(nx<1 || nx>n || ny<1 || ny>m)
                 continue;
             if(nx==n && ny==m)
             {
                 printf("ZZJ到达终点的最短距离是:%d",f[tou].t+1);
                 return;
             }
             if(map[nx][ny]=='.'&&bz[nx][ny]==false)
             {
                 bz[nx][ny]=true;
                 f[wei].x=nx;
                 f[wei].y=ny;
                 f[wei].t=f[tou].t+1;
                 wei++;
             }
         }
         tou++;
     }
}
int main()
{
     scanf("%d%d",&n,&m);
     for(int i=1;i<=n;i++)
     {
         for(int j=1;j<=m+1;j++)
         {
             scanf("%c",&map[i][j]);//结尾要多读一个换行符
         }
     }
     bfs(1,1);
     return 0;
}
```

- 如果理解透了这道题,就练练手吧:
- [题目练习](http://noi.openjudge.cn/ch0205/2753/)
- 鸣谢: @$\text{zhongzijun}$ 。

上一篇:省赛训练1


下一篇:0-1BFS+题目