aciwng 1233. 全球变暖
第九届蓝桥杯省赛C++A/B组,第九届蓝桥杯省赛JAVAA/B组
#include<iostream>
using namespace std;
char g[1010][1010];
int vis[1010][1010];
int n, total, ans;//ans为剩余岛屿,total代表总岛屿数也就是总的连通区域数
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
bool flag = false;
void dfs(int sx, int sy){
int cnt = 0;//利用cnt来计数
for(int i = 0; i < 4; i++){
int nx = sx + dx[i], ny = sy + dy[i];
//这里由于题目给的条件:第一列、行,最后一列、行都是海洋,所以不用做越界处理
if(g[nx][ny] == '#') cnt++;
if(g[nx][ny] == '.' || vis[nx][ny] == 1) continue;
vis[nx][ny] = 1;
dfs(nx, ny);
}
if(cnt == 4) flag = true;//如果上下左右都为陆地
}
int main(){
cin >> n;
for(int i = 0; i < n; i++){
cin >> g[i];
}
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(g[i][j] == '#' && vis[i][j] == 0){//vis[i][j] == 0代表没有被遍历过,说明是在同一个连通区域
dfs(i, j);
total++;
if(flag) ans++;//如果符合剩余岛屿的条件,那么ans++
flag = false;
}
}
}
cout << total - ans << endl;//答案为总岛屿数减去剩下的岛屿数目
return 0;
}