题目描述

你有一张某海域 N×N 像素的照片，”.”表示海洋、”#”表示陆地，如下所示：

.......
.##....
.##....
....##.
..####.
…###.
.......
其中”上下左右”四个方向上连在一起的一片陆地组成一座岛屿，例如上图就有 2 座岛屿。

由于全球变暖导致了海面上升，科学家预测未来几十年，岛屿边缘一个像素的范围会被海水淹没。

具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋)，它就会被淹没。

例如上图中的海域未来会变成如下样子：

.......
.......
.......
.......
....#..
.......
.......
请你计算：依照科学家的预测，照片中有多少岛屿会被完全淹没。

输入格式

第一行包含一个整数N。

以下 N 行 N 列，包含一个由字符”#”和”.”构成的 N×N 字符矩阵，代表一张海域照片，”#”表示陆地，”.”表示海洋。

照片保证第 1 行、第 1 列、第 N 行、第 N 列的像素都是海洋。

输出格式

一个整数表示答案。

数据范围

1≤N≤1000

输入样例1：

7
.......
.##....
.##....
....##.
..####.
…###.
.......

输出样例1：

1

输入样例2：

9
.........
.##.##…
.#####…
.##.##…
.........
.##.#....
.#.###…
.#..#....
.........

输出样例2：

1

C ++ 代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstdio>
#include <cstring>

#define x first
#define y second

using namespace std;
typedef pair<int, int> PII;
const int N = 1010;

int n;
char g[N][N];//地图
bool st[N][N];//是否被遍历过
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

//sx, sy表示初始坐标,lan和bound分别表示当前岛屿陆地和边界的数量
void bfs(int sx, int sy, int &land, int &bound){//flood fill算法
    queue<PII> q;//q表示陆地的集合
    q.push({sx, sy});//将初始位置加入队列
    st[sx][sy] = true;//初始位置已被遍历
    while(q.size()){
        auto t = q.front();
        q.pop();
        land ++;//陆地数量增1
        bool is_bound = false;
        for(int i = 0; i < 4; i ++){
            int x = dx[i] + t.x, y = dy[i] + t.y;
            if(x < 0 || x >= n || y < 0 || y >= n) continue;//越界
            if(st[x][y]) continue;//已被遍历过
            if(g[x][y] == '.'){//边界
                is_bound = true;
                continue;
            }
            q.push({x, y});//将当前点加入队列
            st[x][y] = true;//当前点已被遍历过

        }
        if(is_bound) bound ++;//边界的数量增1

    } 
}

int main(){
//  freopen("abc.txt", "r", stdin);
    cin >> n;
    for(int i = 0; i < n; i ++) scanf("%s", g[i]);

    int cnt = 0;
    for(int i = 0; i < n; i ++){
        for(int j = 0; j < n; j ++){
            if(!st[i][j] && g[i][j] == '#'){//当前点为陆地且未被遍历
                int land = 0, bound = 0;
                bfs(i, j, land, bound);
                if(land == bound) cnt ++;//边界数量和陆地数量相等,即岛屿被淹没
            }
        }
    }

    cout << cnt << endl;

    return 0;
}