蓝桥杯178 全球变暖

题目描述

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

.......

.##....

.##....

....##.

..####.

...###.

.......

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

由于全球变暖导致了海面上升，科学家预测未来几十年，岛屿边缘一个像素的范围会被海水淹没。具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋)，它就会被淹没。

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

.......

.......

.......

.......

....#..

.......

.......

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

输入描述

第一行包含一个整数 N (1≤N≤1000)。

以下 N 行 N 列代表一张海域照片。

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

输出一个整数表示答案。

输入输出样例

示例

输入

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

输出

1

 难。。

1. 遍历整个网格：

   • 遇到未被访问的陆地 (i,j)（c[i][j] == '#' && mem[i][j] == 0），说明发现新岛屿。

   • DFS 探索该岛屿：

     • 递归访问所有相连的陆地。

     • 统计该岛屿中 不会被淹没的陆地数量 flag。

     • 判断陆地是否会被淹没

     • 陆地淹没规则：如果一块陆地 四周至少有一个海洋（'.'），它就会被淹没。

       • 在 dfs(x,y) 中，cnt统计 (x,y) 四周的陆地数量。

       • 如果 cnt== 4（即四周全是陆地），则 (x,y) 不会被淹没 → falg++。

       • 判断岛屿是否完全淹没：

         • 如果 flag== 0（岛屿中没有不会被淹没的陆地），则 ans++（该岛屿会被完全淹没）。

#include
using namespace std;
const int N = 1e3+10;
int n;
char c[N][N];
int mem[N][N];
int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};
int flag;  //统计当前岛屿中不会被淹没的陆地数量
int ans;  //统计会被完全淹没的岛屿数量
void dfs(int x, int y)
{
	int cnt=0;  //统计当前陆地四周的陆地数量
	
	for(int i=0; i>n;
	for(int i=1; ic[i][j];
		}
	}
	 
	for(int i=1; i