【蓝桥杯每日一题】4.2 全球变暖

原题链接：1233. 全球变暖 - AcWing题库

由题意可知：

• 需要找到淹没的岛屿的数量
• 淹没的岛屿所具备的条件：咩有“高地”，也就是说岛屿（连通块）中的所有元素的$4$-邻域中均含有’ . ’

思路1：

将$total$记录岛屿的全部元素数量，$bound$记录岛屿的边界块数量，如果二者相等，则说明该岛屿会被淹没

dfs代码:

#include<bits/stdc++.h>
using namespace std;
const int N=1010;char a[N][N];
bool vis[N][N];
int n;
int res;
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0}; //移动方向
bool flag=false; //插眼，看是否满足周围四个全是#void dfs(int x,int y,int& total,int& bound) //total为联通块个数，bound为边界块个数
{vis[x][y]=1; //记录已经遍历过total++;bool is_bound=false;for(int i=0;i<4;i++){int nx=x+dx[i];int ny=y+dy[i];//边界值的判断if(nx<0||ny<0||nx>=n||ny>n) continue;if(vis[nx][ny]) continue;if(a[nx][ny]=='.') {is_bound=true;continue;}dfs(nx,ny,total,bound);}if(is_bound) bound++;return;
}int main()
{scanf("%d",&n);for(int i=0;i<n;i++) cin>>a[i]; //cin处理字符串更为方便//遍历for(int i=0;i<n;i++){for(int j=0;j<n;j++){if(a[i][j]=='#'&&!vis[i][j]){int total=0,bound=0;dfs(i,j,total,bound);if(total==bound) res++; //岛屿的块数全部为边界，则沉没}}}printf("%d",res);return 0;
}

思路2：

• 直接搜索没有“高地”的连通块，用$flag$值标记一下是否带有“高地”

bfs代码:

#include<bits/stdc++.h>
using namespace std;
const int N=1010;int n;
char a[N][N]; 
int vis[N][N]={0};  
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0}; //移动方向int main()
{scanf("%d",&n);for(int i = 1; i <= n; i++) cin>>a[i]; //cin处理字符串更加方便int res = 0;//进行BFSfor(int i = 1; i <= n; i++) {for(int j = 1; j <= n; j++) {if(a[i][j]=='#' && vis[i][j]==0) {queue<pair<int, int>> q;q.push({i, j});vis[i][j] = 1;bool flag = true;while(!q.empty()) {int x = q.front().first;int y = q.front().second;q.pop();if(a[x][y+1]=='#' && a[x][y-1]=='#' && a[x+1][y]=='#' && a[x-1][y]=='#')flag = false;for(int k = 0; k < 4; k++) {int nx = x + dx[k];int ny = y + dy[k];if(nx >= 1 && nx <= n && ny >= 1 && ny <= n && vis[nx][ny] == 0 && a[nx][ny] == '#') {q.push({nx, ny});vis[nx][ny] = 1;}}}if(flag)res++; // 统计被淹没的岛的数量}}}printf("%d",res);return 0;
}