一、寻找连通块
1. 基本思路
找到一个未被走过的点，以这个点为起点，将与此点相连的所有点标记为走过，答案数 \(+1\)
2. 代码实现
#include <bits/stdc++.h>
using namespace std;
struct p{
int x, y;
};
queue<p> q;
int n, m, cnt;//最终答案为cnt
int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};//方向数组
char mp[1005][1005];//原矩阵
bool f[1005][1005];//标记数组
void bfs(){
while(!q.empty()){
int mx = q.front().x, my = q.front().y;
q.pop();
for(int i = 0; i <= 3; i++){
int nx = mx + dx[i], ny = my + dy[i];
if(nx < 1 || ny < 1 || nx > n || ny > m) continue;
if(mp[nx][ny] =='0') continue;
mp[nx][ny] = '0';//标记此点走过
q.push({nx, ny});
}
}
}
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
cin >> mp[i][j];
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(mp[i][j] != '0'){//未被标记过
cnt++;//答案数+1
q.push({i, j});//以此点为起点
bfs();
}
}
}
cout << cnt;
return 0;
}
例题：
P6757 [BalticOI2013] Tracks in the Snow 雪中足迹
二、经典 bfs 最短路问题
1. 基本思路
以某一格为起点，每步可以向上、下、左、右四个方向走一格，输出到达终点的最少步数。
2. 代码实现
#include <bits/stdc++.h>
using namespace std;
struct p{
int x, y;
};
int n, m, sx, sy, ex, ey, step[1005][1005];
bool mp[1005][1005], f[1005][1005];
int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
// step[i][j]:到达(i,j)的步数
// f[i][j]:(i,j)是否走过
// dx[]/dy[]:方向数组
void bfs(){
queue<p> q;
q.push({sx, sy});
while(!q.empty()){
int mx = q.front().x, my = q.front().y;
q.pop();
if(mx == ex && my == ey){// 到终点
cout << step[mx][my];
return;
}
for(int i = 0; i <= 3; i++){
int nx = mx + dx[i], ny = my + dy[i];
if(nx > n || nx < 1 || ny > m || ny < 1) continue;// 越界的
if(f[nx][ny] || mp[nx][ny]) continue;//走过的/不能走的
f[nx][ny] = 1;// 标记
step[nx][ny] = step[mx][my] + 1;// 步数
q.push({nx, ny});
}
}
}
int main(){
cin >> n;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
cin >> mp[i][j];
cin >> sx >> sy >> ex >> ey;
bfs();
return 0;
}
例题：
3.01bfs
AT_abc176_d [ABC176D] Wizard in Maze
经典的 01bfs 问题。是的你没看错就是之前总结的题（
移步 我的文章。