题目描述

算法1

(bfs) $O(n)$

依次遍历，遍历到陆地，进行bfs，判断是否淹没，已经遍历的点进行记录

C++ 代码

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <set>
#include <queue>
using namespace std;
int n;
char a[1002][1002];
bool b[1002][1002];
typedef pair<int, int> PII;
int flag;
void bfs(int xx,int yy)
{
    int dx[] = { 1,0,-1,0 };
    int dy[] = { 0,1,0,-1 };
    if (a[xx - 1][yy] == '#' && a[xx][yy - 1] == '#' && a[xx + 1][yy] == '#' && a[xx][yy + 1] == '#') {
        flag = 1;
    }
    queue<PII> q;
    b[xx][yy] = true;
    q.push({xx,yy});
    while (q.size()) {
        auto t = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            int x = dx[i] + t.first;
            int y = dy[i] + t.second;
            if (a[x][y] == '.')continue;
            if (b[x][y] == true)continue;
            if (a[x - 1][y] == '#' && a[x][y - 1] == '#' && a[x + 1][y] == '#' && a[x][y + 1] == '#') {
                flag = 1;
            }
            b[x][y] = true;
            q.push({ x,y });
        }
    }
}
int main()
{
    cin >> n;
    int sum = 0;
    char c = getchar();
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            scanf("%c", &a[i][j]);

        }
        c = getchar();
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (b[i][j] == false && a[i][j]=='#') {
                flag = 0;
                bfs(i,j);
                if (flag == 0) {
                    sum++;
                }
            }
        }
    }
    cout << sum;
    return 0;
}