蓝桥杯 10. 全球变暖

全球变暖

原题目链接

题目描述

你有一张某海域 N x N 像素的照片：

• . 表示海洋
• # 表示陆地

例如如下所示：

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

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

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

• 如果一块陆地像素与海洋相邻（上下左右方向中有 .），那么它会被淹没。

例如上述海域未来会变成：

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

请你计算：根据科学家的预测，照片中有多少岛屿会被完全淹没（即该岛屿的所有陆地像素都会被淹没）。

输入描述

• 第一行包含一个整数 N（1 ≤ N ≤ 1000），表示海域为 N x N 像素。
• 接下来 N 行，每行 N 个字符，表示当前海域图像。
• 每个字符为 .（海洋）或 #（陆地）。
• 保证第 1 行、第 1 列、第 N 行、第 N 列的所有像素都是海洋。

输出描述

• 输出一个整数，表示未来会被完全淹没的岛屿数量。

输入示例

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

输出示例

1

c++代码

#include<bits/stdc++.h>

using namespace std;

struct node {
    int sym = 0, index = 0;
};

vector<vector<node>> arr;
string str;
int ans = 0, n;
unordered_set<int> result;

void dfs(int i, int j, int index) {
    if (i < 0 || i >= n || j < 0 || j >= n || arr[i][j].sym == 0 || arr[i][j].index != 0) return;
    arr[i][j].index = index;
    dfs(i + 1, j, index), dfs(i - 1, j, index), dfs(i, j + 1, index), dfs(i, j - 1, index);
}

bool check(int i, int j) {
    if (i - 1 >= 0 && arr[i - 1][j].sym == 0) return true;
    if (i + 1 < n && arr[i + 1][j].sym == 0) return true;
    if (j - 1 >= 0 && arr[i][j - 1].sym == 0) return true;
    if (j + 1 < n && arr[i][j + 1].sym == 0) return true;
    return false;
}

int main() {
    std::ios::sync_with_stdio(false), std::cin.tie(nullptr), std::cout.tie(nullptr);
    cin >> n;
    arr = vector<vector<node>>(n, vector<node>(n));
    for (int i = 0; i < n; i++) {
        cin >> str;
        for (int j = 0; j < n; j++) {
            if (str[j] == '.') arr[i][j].sym = 0;
            else arr[i][j].sym = 1;
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (arr[i][j].sym == 1 && arr[i][j].index == 0) {
                ans++;
                dfs(i, j, ans);
            }
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (arr[i][j].sym == 1) {
                if (check(i, j)) arr[i][j].index = 0;
                if (arr[i][j].index != 0 && result.find(arr[i][j].index) == result.end()) result.insert(arr[i][j].index);
            }
        }
    }
    cout << ans - result.size();
    return 0;
}//by wqs