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

kkxacj · 2023-04-02 16:34:47 · 题解

upd:改进码风，更改错别字。

题目传送门

引言：

这个蒟蒻竟然交了几次才过，写个题解纪念一下。

题意

给出一张某海域 N \times N 像素的照片，求有多少岛屿会被完全淹没。

思路

用 DFS 求出最开始有几个小岛，再求被海水淹没后还剩几个小岛，相减即可得到答案。

注意：被海水淹没后的陆地应用另一个字符表示，而不是把它变为海洋，这个点可以遍历，但不能被当作起点，不然就只有 36 分。

例如：

9
.........
.#######.
.#######.
.#######.
..#.#....
.#######.
.#######.
.#######.
.........

如果你把被淹没的陆地改为海洋的话，后面求就会认为这是两个小岛，答案就会为 -1，但答案其实是 0。

code

#include<bits/stdc++.h>
using namespace std;
int n,ans,ans1;
int fx[6]={-1,0,1,0};
int fy[6]={0,1,0,-1};//方向数组
char d[1010][1010],f[1010][1010]; 
void dfs(int x,int y) //求淹没后有几个大陆 
{
    d[x][y] = '.';
    for(int i = 0;i < 4;i++) 
    {
        int xt = x + fx[i],yt = y + fy[i];
        if(d[xt][yt] != '.' && xt > 0 && xt <= n && yt > 0 && yt <= n) dfs(xt,yt);
    }
    return;
}
void df(int x,int y)//求淹没前有几个大陆 
{
    f[x][y] = '.';
    for(int i = 0;i < 4;i++) 
    {
        int xt = x + fx[i],yt = y + fy[i];
        if(f[xt][yt] == '#' && xt > 0 && xt <= n && yt > 0 && yt <= n) df(xt,yt);
    }
    return;
}
int main()
{
    scanf("%d",&n);
    for(int i = 1;i <= n;i++)
        for(int j = 1;j <= n;j++)
            cin >> d[i][j],f[i][j] = d[i][j];
    for(int i = 1;i <= n;i++)
        for(int j = 1;j <= n;j++) 
            if(d[i][j] == '#' && (d[i-1][j] == '.' || d[i+1][j] == '.' || d[i][j-1] == '.' || d[i][j+1] == '.')) 
                d[i][j] = '-'; 
    for(int i = 1;i <= n;i++)
        for(int j = 1;j <= n;j++)
            if(f[i][j] == '#')
            {
                ans1++;
                df(i,j);
            }
    for(int i = 1;i <= n;i++)
        for(int j = 1;j <= n;j++)
            if(d[i][j] == '#')
            {
                ans++;
                dfs(i,j);
            }
    printf("%d",ans1 - ans);
    return 0;
}