题目描述

给定一个图,’#’代表陆地，’.’代表海洋，如果陆地的上、下、左、右的任意一个方向是海洋则
这一块陆地会被淹没，初始状态下会有若干个连通块求得会被淹没的连通块数量（连通块与陆地的关系：一个或多个陆地组成一个连通块）

样例

.......
.##....
.##....
....##.
..####.
...###.
.......

图中有两个连通块，左上方的连通块会被淹没

算法

(BFS) $O(n^2)$

blablabla

C++ 代码

//1.遍历每一个点,如果遇到了没有处理过的陆地则对其进行检查 
//2.检查时记录连通块中陆地的数量total(进队的元素个数)
//  被淹没的陆地的数量bound(如果某个陆地的任意一个方向是海洋则会被淹没)
//3.如果连通块的total == bound则计数器++ 

#include <iostream>
#include <queue>

using namespace std;

const int N = 1e4+10;

typedef pair<int,int> PII;

int n,cnt;
char g[N][N];//存储图 
bool st[N][N];//存储该点是否被检查过 
int dx[4] = {-1,0,1,0},dy[4] = {0,1,0,-1};

void BFS(int x,int y,int &total,int &bound) 
{
    queue<PII> q;
    q.push({x,y});//起点入队
    st[x][y] = true;
    while(!q.empty()) 
    {
        auto t = q.front();
        q.pop();//移除队首元素  
        total++;//总陆地数量  
        bool is_bound = false;//假设最初这块陆地不会被淹没 
        for(int i = 0; i < 4; i++)
        {
            int tx = t.first + dx[i],ty = t.second + dy[i];//新点
            //在矩阵内、未被检查过  
            if(tx >= 1 && tx <= n && ty >= 1 && ty <= n && !st[tx][ty])
            {
                if(g[tx][ty] == '.') is_bound = true;
                else
                {
                    q.push({tx,ty});
                    st[tx][ty] = true;
                }
            }
        }
        if(is_bound) bound++;
    }
}

int main()
{
    cin >> n;

    for(int i = 1; i <= n; i++) 
        for(int j = 1; j <= n; j++)
            cin >> g[i][j];

    for(int i = 1; i <= n; i++) 
        for(int j = 1; j <= n; j++)
            if(!st[i][j] && g[i][j] == '#')
            {//如果没有被检查过且是陆地 
                int total = 0,bound = 0;
                BFS(i,j,total,bound);
                if(total == bound) cnt++;
            }

    cout << cnt << endl;
    return 0;
}