广度优先搜索 (BFS) 从入门到进阶
题单介绍
## 广度优先搜索 (BFS) 从入门到进阶
**本题单不涉及图论，有需要见[这里](https://www.luogu.com.cn/training/list?type=select&keyword=%E5%9B%BE%E8%AE%BA&page=1)**
#### 1. 模板广搜
+ [P1746 离开中山路](https://www.luogu.com.cn/problem/P1746)
+ [B3625 迷宫寻路](https://www.luogu.com.cn/problem/B3625)
+ [P1699 [USACO19OPEN] Bucket Brigade B](https://www.luogu.com.cn/problem/P1699)
#### 2.模板稍微变形广搜
+ [P2802 回家](https://www.luogu.com.cn/problem/P2802)
+ [P8673 [蓝桥杯 2018 国 C] 迷宫与陷阱](https://www.luogu.com.cn/problem/P8673)
+ [P1443 马的遍历](https://www.luogu.com.cn/problem/P1443)
+ [P10491 [USACO09NOV] The Chivalrous Cow B](https://www.luogu.com.cn/problem/P10491)
+ [P1747 好奇怪的游戏](https://www.luogu.com.cn/problem/P1747#submit)
#### 3.模板广搜变形
+ [B3626 跳跃机器人](https://www.luogu.com.cn/problem/B3626)
+ [P1135 奇怪的电梯](https://www.luogu.com.cn/problem/P1135)
+ [P1825 [USACO11OPEN] Corn Maze S](https://www.luogu.com.cn/problem/P1825)
+ [P2895 [USACO08FEB] Meteor Shower S](https://www.luogu.com.cn/problem/P2895)
+ [P7243 最大公约数](https://www.luogu.com.cn/problem/P7243)
+ [P9107 [PA2020] Wycieczka górska](https://www.luogu.com.cn/problem/P9107)
---------------------------------------
如果你掌握了以上题目，则可以尝试完成以下题目
**对标 CSP-J T3/T4 或者 CSP-S**
+ [P1126 机器人搬重物](https://www.luogu.com.cn/problem/P1126)
+ [P2199 最后的迷宫](https://www.luogu.com.cn/problem/P2199#submit)
+ [P3956 [NOIP2017 普及组] 棋盘](https://www.luogu.com.cn/problem/P3956)
+ [P3855 [TJOI2008] Binary Land](https://www.luogu.com.cn/problem/P3855)
+ [P8693 [蓝桥杯 2019 国 AC] 大胖子走迷宫](https://www.luogu.com.cn/problem/P8693)
+ [P1514 [NOIP2010 提高组] 引水入城](https://www.luogu.com.cn/problem/P1514)
+ [P2749 [USACO5.1] 夜空繁星Starry Night](https://www.luogu.com.cn/problem/P2749)
+ [P2845 [USACO15DEC] Switching on the Lights S](https://www.luogu.com.cn/problem/P2845)
+ [P3716 [CTSC2000] 冰原探险](https://www.luogu.com.cn/problem/P3716)
#### 最后附一个广搜模板
```cpp
struct node{
int x,y,step;
};
int bfs(int x,int y){
queue<node> q;
q.push({x,y,0});
bool vis[N][N];
memset(vis,false,sizeof(vis));
vis[x][y]=true;
while(q.size()){
node dt=q.front();
q.pop();
if(dt.x==ex&&dt,y==ey) return dt.step;
for(int i = 0;i < 4;++i){
int xx=dt.x+dx[i];
int yy=dt.y+dy[i];
if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&a[xx][yy]=='.'&&!vis[xx][yy]){
q.push({xx,yy,dt.step+1});
vis[xx][yy]=true;
}
}
}
return -1;
}
```