BFS的联通块问题（模板）
1 #include <bits/stdc++.h>
2 using namespace std;
3 struct node {
4 int x;
5 int y;
6 };
7 queue<node> Q;
8 const int maxn=200;
9 int maap[maxn][maxn];
10 bool book[maxn][maxn]= {false};
11 int m,n;
12 int next[4][2]= {
13 0,-1,
14 0,1,
15 -1,0,
16 1,0
17 };
18 void bfs(int x1,int y1)
19 {
20 node nn;
21 nn.x=x1;
22 nn.y=y1;
23 while(!Q.empty()) Q.pop();
24 Q.push(nn);
25 book[x1][y1]=true;
26 while(Q.empty()==false)
27 {
28 node now=Q.front();
29 Q.pop();
30 for(int i=0; i<4; i++)
31 {
32 int nx=now.x+next[i][0];
33 int ny=now.y+next[i][1];
34 if(nx<0 || nx>m-1 || ny<0 || ny>n-1)
35 {
36 continue;
37 }
38 if(maap[nx][ny]==0 || book[nx][ny]==true)
39 {
40 continue;
41 }
42 node final;
43 final.x=nx;
44 final.y=ny;
45 book[nx][ny]=true;
46 Q.push(final);
47 }
48 }
49 }
50 int main() {
51 cin>>m>>n;
52 for(int i=0; i<m; i++)
53 {
54 for(int j=0; j<n; j++)
55 {
56 cin>>maap[i][j];
57 }
58 }
59 int ans=0;
60
61 for(int i=0; i<m; i++)
62 {
63 for(int j=0; j<n; j++)
64 {
65 if(maap[i][j]==1 && book[i][j]==false)
66 {
67 bfs(i,j);
68 ans++;
69 }
70 }
71 }
72 cout<<ans<<endl;
73 return 0;
74 }
BFS的计步（最短路）问题（模板）
1 #include <bits/stdc++.h>
2 using namespace std;
3 const int maxn=100;
4 //最大尺寸
5 queue<int> qx,qy;
6 //横纵坐标队列
7 int stx,sty,edx,edy;
8 //起点终点坐标
9 bool vis[maxn+10][maxn+10];
10 //访问标记
11 int maap[maxn+10][maxn+10];
12 //零一迷宫
13 int n,m;
14 //尺寸
15 int direx[]={1,0,-1,0};
16 int direy[]={0,1,0,-1};
17 //四向联通
18 int range[maxn+10][maxn+10];
19 //当前查找深度
20 int end_range=-1;
21 //最终深度
22 void bfs(int stx,int sty)
23 {
24 vis[stx][sty]=true;
25 qx.push(stx);
26 qy.push(sty);
27 //起点压入队列
28 range[stx][sty]=0;
29 //起点查找深度
30 while(!qx.empty())
31 //队列的最后一个元素没被弹出去
32 {
33 for(int i=0;i<4;i++)
34 //四向联通入队列
35 {
36 int x_now=qx.front()+direx[i];
37 int y_now=qy.front()+direy[i];
38 //进入附近块
39 if(x_now>= 1&& x_now<=n && y_now>=1&&y_now<=m&&maap[x_now][y_now]!=0&&!vis[x_now][y_now])
40 //不出界非障碍未访问
41 {
42 vis[x_now][y_now]=true;
43 //打访问标记
44 qx.push(x_now);
45 qy.push(y_now);
46 //压入队列
47 end_range=range[x_now][y_now]=range[qx.front()][qy.front()]+1;
48 }
49 }
50 qx.pop();
51 qy.pop();
52 //弹出已经被搜完的元素
53 }
54 return;
55 }
56 int main()
57 {
58 cin>>n>>m;
59 for(int i=1;i<=n;i++)
60 {
61 for(int j=1;j<=m;j++)
62 {
63 cin>>maap[i][j];
64 }
65 }
66 cin>>stx>>sty>>edx>>edy;
67 bfs(stx,sty);
68 cout<<end_range<<endl;
69 return 0;
70 }
