1 #include<iostream> 2 #include<stdio.h> 3 #include<stdlib.h> 4 #include<time.h> 5 #include <queue> 6 using namespace std; 7 int N,ans=0; 8 int ax[4]={0,0,1,-1}; 9 int ay[4]={1,-1,0,0}; 10 //bfs队列加对象，对象就是队列的类型，在这个题中就可以直接用x,y 11 //满足条件（为#）的对象插入队列 12 struct Point{ 13 int x; 14 int y; 15 }; 16 queue<Point> q; 17 //标记是否到达 18 int mark[100][100]={0}; 19 char data[100][100]; 20 21 22 void bfs(int i,int j){//bfs的返回值设为void 是因为你可以把它要更改的全部数据设置为全局变量 23 //首次进来标记为已访问,并且要插入队列 24 mark[i][j]=1; 25 q.push({i,j}); 26 int cnt1=0; 27 int cnt2=0; 28 while(!q.empty()){//这里是循环，直到队列为空．所以其实bfs函数就执行了一次 29 Point first=q.front();//取头 30 q.pop();//弹出 31 cnt1++; 32 bool bound=false;//标记其是否有#,因为有一个#就可以判断沉了 33 for (int k = 0; k < 4; ++k) { 34 int x=first.x+ax[k]; 35 int y=first.y+ay[k];//这个地方一开始写错．注意是取的first的两个量在改变而不是ij 36 //对每一个位置，判断是否越界以及是哪种字符 37 if(x>=0 && x<N && y>=0 && y<N && data[x][y]=='.')//本未是否可行 38 bound =true; 39 if(x>=0 && x<N && y>=0 && y<N && data[x][y]=='#' && mark[x][y]==0){//周围有没有可以放在队列里的 40 q.push({x,y}); 41 mark[x][y]=1;//一开始忘记了，注意标注 42 } 43 } 44 if(!bound) { 45 cnt2++; 46 47 } 48 49 } 50 ans=cnt2; 51 // cout<<cnt2<<endl; 52 53 54 } 55 int main(){ 56 cin>>N; 57 for (int i = 0; i < N; ++i) { 58 for (int j = 0; j < N; ++j) { 59 cin>>data[i][j]; 60 61 } 62 63 } 64 for (int i = 0; i < N; ++i) { 65 for (int j = 0; j < N; ++j) { 66 67 if (data[i][j] == '#' && mark[i][j] == 0) { 68 bfs(i,j); 69 70 // cout << i<<" "<<j<<endl; 71 //bfs(i,j);//所有的都要遍历，防止孤零零一个#被卡出来 72 } 73 74 } 75 } 76 77 78 79 cout<<ans; 80 81 }
bfs连通块问题，，，，，
如果是要求有几个连通块就是进bfs()了几次
如果需要进行标记就是用全局变量
队列里的循环：
先取头去头，
然后对头进行四个方向的判断：
1.是否可以加入队列（一定要注意边界，有些题边界是可以加入队列的，比如这个题．但这个题限制不可能在边界了呜呜呜，一开始错了耗了好久）
2.是否满足条件．
只有加入队列才有资格判断是否满足条件．
注意一个技巧就是queue放入的对象是一个结构体．