P8662 [蓝桥杯 2018 省 AB] 全球变暖 题解

· · 题解

分析

简单的暴力题。

思路很简单，如果一块陆地上下左右都是陆地，就算与他相邻的陆地都被淹没，那这块地也不会被淹，这个小岛就没有被完全淹没。所以我们只需要遍历一遍，看每个岛的陆地是否沿海即可。

直接 DFS，实现方法详见代码。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1005;
char a[N][N];
int n,ans,xx[] = {1,-1,0,0},yy[] = {0,0,1,-1};
bool v = 1,vis[N][N];//v来记录返回值，vis数组打标记 
bool ok(int x,int y)//单纯是为了方便，判断是否是陆地 
{
    return a[x][y]!='.';
}
bool dfs(int x,int y)
{
    vis[x][y] = 1;//遍历过了，标记为1 
    if(ok(x-1,y)&&ok(x+1,y)&&ok(x,y-1)&&ok(x,y+1))//上下左右都是陆地，不沿海，那么这个岛不会被完全淹没 
        v = 0;
    for(int i = 0;i<4;i++)//扩张 
    {
        int X = x+xx[i],Y = y+yy[i]; 
        if(ok(X,Y)&&vis[X][Y]==0)//没遍历过并且是陆地，那么此区域属于这片岛屿 
            dfs(X,Y);
    }
    a[x][y] = '.'; 
    return v;
}
signed main()
{
    cin>>n;
    for(int i = 1;i<=n;i++)
        for(int j = 1;j<=n;j++)
            cin>>a[i][j];
    for(int i = 1;i<=n;i++)
        for(int j = 1;j<=n;j++)
            if(ok(i,j))//如果是陆地，那么就遍历这个岛 
                v = 1,ans+=dfs(i,j);
    cout<<ans;
    return 0;
}