概念
breadth first search(bfs) 宽度优先搜索。算法过程可以看做是图上火苗传播的过程:最开始只有起点着火了,在每一时刻,有火的节点都向它相邻的所有节点传播火苗。
这块应该先去了解一下图上的遍历的过程,更好理解代码
棋盘问题,Flood Fill,问题状态的表述升级,模型主要特点,最短路/最少步数/最少次数,就是图论最短路问题,边权是1的情况。
根据下面示例代码,学习bfs(),学会使用queue<>。bfs相对是好写的,模板很清晰。
《一本通》题目
【例8.2】细胞
// Flood Fill
// 示例代码
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 1e4 + 10;
char s[N][N];
int n, m; //没有给nm范围
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
void bfs(int ux, int uy)
{
queue<PII> q;
q.push(make_pair(ux, uy));
while (!q.empty()){
PII t = q.front(); q.pop();
int x = t.first, y = t.second;
s[x][y] = '0';
for (int i = 0; i < 4; i++){
int a = x + dx[i], b = y + dy[i];
if (a < 0 || a >= n || b < 0 || b >= m) continue;
if (s[a][b] == '0') continue;
q.push(make_pair(a, b));
}
}
}
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i++) scanf("%s", s[i]);
int cnt = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++){
if (s[i][j] != '0'){
bfs(i, j);
cnt++;
}
}
cout << cnt << '\n';
return 0;
}
【例8.3】最少步数
//棋盘问题,最短路
Dungeon Master
//棋盘问题,最短路
Lake Counting
//Flood Fill
The Castle
//Flood Fill,位运算
仙岛求药
//棋盘问题,最短路,多组测试数据
走迷宫
//棋盘问题,最短路,一组测试数据
抓住那头牛
//最短路问题,问题空间转换为数轴上运动
走出迷宫
//棋盘问题,最短路
迷宫问题
//棋盘问题,打印路径
献给阿尔吉侬的花束
//棋盘问题,最短路,T组数据
Knight Moves
//棋盘问题,最短路,8个方位
《517》题目
拼图游戏
//对拼图的编码,解码,开哈希,移动拼图的模拟。此题能够独立写出来,标志这bfs过关
类似的题目有:
洛谷:八数码难题, acwing:AcWing 845. 八数码
营救计划
//迷宫问题,遇到守卫还是道路分类讨论
倒酒
//锻炼问题状态的理解,三个酒杯的状态表述,模拟三个酒杯互相倒酒的枚举过程。一道好题。