LQB201808全球变暖　bfs

 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 }