题目描述

样例

#include<iostream>
#include<string>
using namespace std;
int n,res = 0;
const int N = 1010;
char str[N][N];
bool v[N][N];
bool flag = true;
int dx[4] = {0,1,0,-1},dy[4] = {1,0,-1,0};
void change(int x,int y)//染色，海水淹没的地方置为*
{

    for(int i = 0;i < 4;i++)
    {
        int x1 = dx[i] + x;
        int y1 = dy[i] + y;
        if(x1 >= 0 && y1 >= 0 &&  x1 < n && y1 < n && str[x1][y1] == '.')
        {
            str[x][y] = '*'; 
        }
    }
}
void dfs(int x,int y)
{
    for(int i = 0;i < 4;i++)
    {
        int x1 = dx[i] + x;
        int y1 = dy[i] + y;
        if(x1 >= 0 && y1 >= 0 &&  x1 < n && y1 < n && (str[x1][y1] == '#' || str[x1][y1] == '*'))
        {
            if(str[x1][y1] == '#')//发现陆地存在
            flag = false;
            str[x1][y1] = '.'; //染色避免重复访问
            dfs(x1,y1);

        }
    }
}
int main()
{
    cin >> n;
    int count = 0;
    for(int i = 0;i < n;i++)
    cin >> str[i];
    for(int i = 0;i < n;i++)
    {
        for(int j = 0;j < n;j++)
        {
            if(str[i][j] == '#')
            {
                change(i,j);
            }
        }
    }

    for(int i = 0;i < n;i++)
    {
        for(int j = 0;j < n;j++)
        {
            flag = true;
            if(str[i][j] == '*')//重新遍历原来的陆地
            {
                count++;//count记录的是岛屿个数
                str[i][j] = '.';
                dfs(i,j);
            }
            if(!flag)
            res++;//记录的是未被淹没的陆地个数
        }
    }
    cout << count -res;

}