全球变暖
原题目链接
题目描述
你有一张某海域 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
