題目描述

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

.......

.##....

.##....

....##.

..####.

...###.

.......

其中"上下左右"四個方向上連在一起的一片陸地組成一座島嶼。例如上圖就有 2 座島嶼。

由于全球變暖導致了海面上升，科學家預測未來幾十年，島嶼邊緣一個像素的范圍會被海水淹沒。具體來說如果一塊陸地像素與海洋相鄰(上下左右四個相鄰像素中有海洋)，它就會被淹沒。

例如上圖中的海域未來會變成如下樣子：

.......

.......

.......

.......

....#..

.......

.......

請你計算：依照科學家的預測，照片中有多少島嶼會被完全淹沒。

輸入描述

第一行包含一個整數?N?(1≤N≤1000)。

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

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

輸出一個整數表示答案。

輸入輸出樣例

示例

輸入

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

輸出

1

?

?難。。

1. 遍歷整個網格：

   • 遇到未被訪問的陸地?(i,j)（c[i][j] == '#' && mem[i][j] == 0），說明發現新島嶼。

2. DFS 探索該島嶼：

   • 遞歸訪問所有相連的陸地。

   • 統計該島嶼中?不會被淹沒的陸地數量?flag。

   • 判斷陸地是否會被淹沒

   • 陸地淹沒規則：如果一塊陸地?四周至少有一個海洋（'.'），它就會被淹沒。

     • 在?dfs(x,y)?中，cnt統計?(x,y)?四周的陸地數量。

     • 如果?cnt== 4（即四周全是陸地），則?(x,y)?不會被淹沒?→?falg++。

3. 判斷島嶼是否完全淹沒：

   • 如果?flag== 0（島嶼中沒有不會被淹沒的陸地），則?ans++（該島嶼會被完全淹沒）。

#include<iostream>
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<4; i++){int nx=x+dx[i];int ny=y+dy[i];if(nx<1 || ny<1 || nx>n || ny>n) continue;  //越界 if(c[nx][ny]=='.')  //如果是海洋{mem[nx][ny]=1; continue;}if(c[nx][ny]=='#')   //如果是陸地{cnt++;  //增加四周陸地計數if(mem[nx][ny]==0){mem[nx][ny]=1;dfs(nx, ny);} }		}//如果當前陸地四周都是陸地，增加不會被淹沒的陸地數量if(cnt==4) flag++;
}int main()
{cin>>n;for(int i=1; i<=n; ++i){for(int j=1; j<=n; ++j){cin>>c[i][j];}}for(int i=1; i<=n; ++i){for(int j=1; j<=n; ++j){//如果當前位置是陸地且未被訪問（說明這塊陸地屬于一個新的島嶼） if(c[i][j]=='#' && mem[i][j]==0){flag=0;  //重新統計該島嶼中不會被淹沒的陸地數量 dfs(i, j);if(flag==0) ans++;  //如果島嶼中不會被淹沒的陸地為0，說明會被完全淹沒}}} cout<<ans;return 0;
}