题目描述
你有一张某海域 N×N 像素的照片，
.表示海洋、#表示陆地，如下所示：....... .##.... .##.... ....##. ..####. ...###. .......其中 "上下左右" 四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有 2 座岛屿。
由于全球变暖导致了海面上升，科学家预测未来几十年，岛屿边缘一个像素的范围会被海水淹没。具体来说如果一块陆地像素与海洋相邻（上下左右四个相邻像素中有海洋），它就会被淹没。
例如上图中的海域未来会变成如下样子：
....... ....... ....... ....... ....#.. ....... .......请你计算：依照科学家的预测，照片中有多少岛屿会被完全淹没。
输入格式
第一行包含一个整数 N。(1≤N≤1000)。
以下 N 行 N 列代表一张海域照片。
照片保证第 1 行、第 1 列、第 N 行、第 N 列的像素都是海洋。
输出格式
一个整数表示答案。
输入输出样例
输入 #1复制
7 ....... .##.... .##.... ....##. ..####. ...###. .......输出 #1复制
1说明/提示
时限 1 秒, 256M。蓝桥杯 2018 年第九届省赛
代码解析+注释
#include<bits/stdc++.h>
using namespace std;// 定义最大网格尺寸
const int N = 1e3 + 10;// 定义网格数组和相关变量
char a[N][N]; // 存储网格
int n, ans; // n: 网格的大小，ans: 满足条件的区域数量
// xx[], yy[] 用于表示四个方向：下、上、右、左
int xx[] = {1, -1, 0, 0};
int yy[] = {0, 0, 1, -1};// vis[] 数组用于标记某个位置是否已被访问过
bool v = 1, vis[N][N];// 检查当前位置是否是 '#'
bool ok(int x, int y) {return a[x][y] != '.'; // 如果当前格子是 '#', 返回true，否者返回false
}// 深度优先搜索（DFS）函数，遍历与当前格子相连的所有 '#'
bool dfs(int x, int y) {vis[x][y] = 1; // 标记当前位置已访问// 如果当前格子的四个方向（上下左右）都被 '#' 包围if (ok(x-1, y) && ok(x+1, y) && ok(x, y+1) && ok(x, y-1))v = 0; // 如果四个方向都被 '#' 围住，表示不符合条件，设置 v = 0// 遍历四个相邻的格子for (int i = 0; i < 4; i++) {int X = x + xx[i], Y = y + yy[i]; // 计算相邻位置的坐标// 如果相邻格子是 '#' 且没有被访问过if (ok(X, Y) && !vis[X][Y]) {dfs(X, Y); // 递归地访问相邻格子}}a[x][y] = '.'; // 当前格子处理完毕，标记为 '.'，表示已处理return v; // 返回是否符合条件的标志
}signed main() {cin >> n; // 输入网格的大小 n// 输入网格的内容for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {cin >> a[i][j]; // 读取网格每个位置的值}}// 遍历整个网格for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {// 如果当前位置是 '#'if (ok(i, j)) {v = 1; // 假设满足条件ans += dfs(i, j); // 调用DFS，递归遍历当前区域}}}cout << ans << endl; // 输出满足条件的区域数量return 0;
}
