题目描述

2021想法：
按照floodfill算法，我们把淹没的#替换成*而不是海洋.，这样我们在寻找某一个陆地周围是否有四个路地时，就可以直接！=’.’即可。这样就避免我们在floodfill时如果提前替换成.而造成之后的寻找“一个陆地周围是否有四个路地时”这一过程出现错误。

2020想法：
题意就不在赘述，这里分享一下如何用DFS解这道题
1.首先先找到有哪一个’#’号，是上下左右都是’#’号的
2.通过他进行DFS把和他周围联通的’#’全部用st数组标记，代表了这个连通块是不会被淹没的
3.重复1过程，找到剩余的且没有被标记合法(上下左右都是’#’)的’#’并且进行2过程
4.统计搜索到了多少’#’就是有多少个不会淹没的连通块
5.最后DFS统计总共有多少个连通块，相减得到答案

样例

输入样例1：

7
.......
.##....
.##....
....##.
..####.
...###.
.......

输出样例1：

1

输入样例2：

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

输出样例2：

1

算法1

(dfs)

C++ 代码

//2021
#include <iostream>


using namespace std;

int n;
int cnt2 = 0;
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
char c[1100][1100];
int flag = 0;

void dfs1(int x, int y)
{
    if(c[x-1][y] != '.' && c[x][y-1] != '.' && c[x][y+1] != '.' && c[x+1][y] != '.'&&!flag) 
    {
        cnt2++;
        flag=1;
    }
    for(int i = 0; i < 4; i++)
    {
        int tx = x + dx[i];
        int ty = y + dy[i];
        if(tx < 0 || tx >=n || ty < 0 || ty >= n || c[tx][ty] != '#' ) 
        {
            continue;    
        }
        c[tx][ty]='*';
        dfs1(tx, ty);

    }
}



int main()
{
    cin>>n;
    for(int i = 0; i < n; i ++ )
    {
        for(int j = 0; j < n; j ++ )
        {
            cin>>c[i][j];
        }
    }
    int cnt = 0;
    for(int i = 0; i < n; i ++ )
    {
        for(int j = 0; j < n; j ++ )
        {

            if(c[i][j] == '#')
            {
                flag = 0;
                dfs1(i,j);
                cnt++;
            }
        }
    }
    cout<<cnt-cnt2<<endl;
    return 0;
}

//2020
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1100;
bool st[N][N];
int n,m;
int q;
int dx[5]={0,-1,1,0,0};
int dy[5]={0,0,0,-1,1};
char c[N][N];
int flag=0;

bool check(int x,int y)
{
    for(int i=1;i<=4;i++)
    {
        int tx=x+dx[i];
        int ty=y+dy[i];
        if(tx<1||tx>n||ty<1||ty>n) return false;
        if(c[tx][ty]=='.') return false;
    }
    return true;
}
void dfs(int x,int y)
{
    for(int i=1;i<=4;i++)
    {
        int tx=x+dx[i];
        int ty=y+dy[i];
        if(tx<1||tx>n||ty<1||ty>n) continue;
        if(st[tx][ty]==true) continue;
        if(c[tx][ty]=='.')  continue;
        st[tx][ty]=true;
        //cout<<tx<<" "<<ty<<" "<<st[tx][ty]<<endl;
        dfs(tx,ty);

    }
}
void dfs1(int x,int y)
{
    c[x][y]='.';
    for(int i=1;i<=4;i++)
    {
        int tx=x+dx[i];
        int ty=y+dy[i];
        if(tx<1||tx>n||ty<1||ty>n) continue;
        if(c[tx][ty]=='.')  continue;
        dfs1(tx,ty);
    }
}
int main()
{
    cin>>n;
    int cnt=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cin>>c[i][j];
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(c[i][j]=='#'&&!st[i][j]&&check(i,j))
            {
                st[i][j]=true;
                cnt++;
                dfs(i,j);
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(c[i][j]=='#')
            {
                ans++;
                dfs1(i,j);
            }
        }
    }
    //cout<<cnt<<" "<<ans<<endl;
    cout<<ans-cnt<<endl;
    return 0;
}