【蓝桥杯每日一题】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;
    
    //进行BFS
    for(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;
}