1233. 全球变暖
你有一张某海域 N×N 像素的照片，”.”表示海洋、”#”表示陆地，如下所示：
.......
.##....
.##....
....##.
..####.
...###.
.......
其中”上下左右”四个方向上连在一起的一片陆地组成一座岛屿，例如上图就有 2 座岛屿。
由于全球变暖导致了海面上升，科学家预测未来几十年，岛屿边缘一个像素的范围会被海水淹没。
具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋)，它就会被淹没。
例如上图中的海域未来会变成如下样子：
.......
.......
.......
.......
....#..
.......
.......
请你计算：依照科学家的预测，照片中有多少岛屿会被完全淹没。
输入格式
第一行包含一个整数N。
以下 N 行 N 列，包含一个由字符”#”和”.”构成的 N×N 字符矩阵，代表一张海域照片，”#”表示陆地，”.”表示海洋。
照片保证第 1 行、第 1 列、第 N 行、第 N 列的像素都是海洋。
输出格式
一个整数表示答案。
数据范围
1≤N≤1000
输入样例1：
7
.......
.##....
.##....
....##.
..####.
...###.
.......
输出样例1：
1
输入样例2：
9
.........
.##.##...
.#####...
.##.##...
.........
.##.#....
.#.###...
.#..#....
.........
输出样例2：
1
题目分析
对于每个点进行遍历，并进行标记
查看当前点能够达到的其他陆地，如果当前的陆地周围相邻海水，则说明该陆地会被淹没，因此我们在对点进行遍历的时候，只需要记录周围相邻海水的陆地数量和总的陆地数量是否相等即可，如果相等则说明该岛屿会被完全淹没，反之则不会被完全淹没
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<stack>
#include<queue>
#include<sstream>#define x first
#define y secondusing namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 1010;
const int MOD = 1000000007;
const int INF = 0x3f3f3f3f;int n;
char g[N][N];
bool st[N][N];int dx[] = {
1, 0, -1, 0};
int dy[] = {
0, 1, 0, -1};void bfs(int sx, int sy, int &total, int &bound)
{
queue<PII> q;q.push({
sx, sy});st[sx][sy] = true;while(!q.empty()){
PII t = q.front();q.pop();total ++ ;bool is_bound = false;for(int i = 0; i < 4; i ++ ){
int x = t.first + dx[i];int y = t.second + dy[i];if(x < 0 || y < 0 || x >= n || 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 ++ ;}
}int main()
{
cin >> n;for(int i = 0; i < n; i ++ ){
for(int j = 0; j < n; j ++ ){
cin >> g[i][j];}}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 total = 0, bound = 0;bfs(i, j, total, bound);if(total == bound) cnt ++ ;}}}cout << cnt << endl;return 0;
}