-
题目描述
- 你有一张某海域NxN像素的照片，”.”表示海洋、”#”表示陆地，如下所示：
…….
.##….
.##….
….##.
..####.
…###.
…….
其中”上下左右”四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有2座岛屿。
由于全球变暖导致了海面上升，科学家预测未来几十年，岛屿边缘一个像素的范围会被海水淹没。具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋)，它就会被淹没。
例如上图中的海域未来会变成如下样子：
…….
…….
…….
…….
….#..
…….
…….
请你计算：依照科学家的预测，照片中有多少岛屿会被完全淹没。
【输入格式】
第一行包含一个整数N。 (1 <= N <= 1000)
以下N行N列代表一张海域照片。
照片保证第1行、第1列、第N行、第N列的像素都是海洋。
【输出格式】
一个整数表示答案。
1
2
3
4
5
6
7
8
【输入样例】
7
…….
.##….
.##….
….##.
..####.
…###.
…….
【输出样例】
1
代码块
代码块语法遵循标准markdown代码，例如：
“`
C++
include
include
using namespace std;
char a[1000][1000];
int n;
int i,j;
int x=0,y=0;
int b[1000]={0};
int c[1000]={0};
void find(int i,int j){
if(i<0||j<0||i>=n||j>=n){
return ;
}
if(a[i][j]==’#’){
if((a[i+1][j]==’#’)&&(a[i-1][j]==’#’)&&(a[i][j-1]==’#’)&&(a[i][j+1]==’#’)){//用来寻找周围不会别淹没的岛屿。
b[x++]=i;
c[y++]=j;
return ;
}
else{
return ;
}
}
}
void dfs(int i,int j){//用DFS遍历岛屿的个数。
if(i<0||j<0||i>=n||j>=n){
return ;
}
if(a[i][j]==’#’){
a[i][j]=’.’;
dfs(i+1,j);
dfs(i-1,j);
dfs(i,j-1);
dfs(i,j+1);
}
}
int main(){
cin>>n;
for(i=0;i