2018蓝桥杯C++A组——全球变暖

本文主要是介绍2018蓝桥杯C++A组——全球变暖，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

问题描述

【题目描述】

【输入】

【输出】

【样例输入】

7 
.......
.##....
.##....
....##.
..####.
...###.
.......  

【样例输出】

1

题目解析

这道题可以理解成连通块问题。针对每一个连通块采用$bfs$遍历方法动态模拟淹没的过程。

准备$data[]$数组记录地图数据，$mark[]$数组标记是否访问过。

双重循环遍历$data[]$数组当$data[]==\#$且$mark[]==0$时就调用$bfs()$宽度优先遍历四周的岛屿。

具体代码如下：

C++代码

#include<bits/stdc++.h>
using namespace std;
int N,ans; //规模，答案
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
char data[1000][1000];
int mark[1000][1000];
struct Point
{int x,y;
};
void bfs(int i,int j)
{mark[i][j] = 1;//标记为已访问queue<Point> q; //新建一个队列q.push({i,j}); //将当前格子封装到Point中并插入队列int cnt1=0,cnt2=0; //分别记录当前这个连通块#的数量以及和.相邻的#的数量while(!q.empty()){Point first = q.front();q.pop();cnt1++;bool swed = false; //标记弹出的#四周是否有.for(int k=0;k<4;k++) //向四周探测{int x = first.x+dx[k];int y = first.y+dy[k];if(x>=0&&x<N&&y>=0&&y<N&&data[x][y]=='.') swed = true;//周边的#如果未被访问将其加入队列if(x>=0&&x<N&&y>=0&&y<N&&data[x][y]=='#'&&mark[x][y]==0){q.push({x,y});mark[x][y]=1;}}if(swed) cnt2++;}//一个连通块就被访问完毕，#的数量记录在cnt1，周边有.的数量记录在cnt2if(cnt1==cnt2) ans++;
}
void work()
{std::ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>N; //读取规模char next; //读换行符cin.get(next);while(next!='\n') cin.get(next);for(int i=0;i<N;i++) //双循环读地图数据{for(int j=0;j<N;j++)cin.get(data[i][j]);cin.get(next);while(next!='\n') cin.get(next);}for(int i=0;i<N;i++) //从#开始宽度优先搜索for(int j=0;j<N;j++)if(mark[i][j]==0&&data[i][j]=='#')bfs(i,j);cout<<ans<<endl;
}
int main()
{work();return 0;
}

结果

这篇关于2018蓝桥杯C++A组——全球变暖的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---