题目描述

你有一张某海域 N×N

像素的照片，”.”表示海洋、”#”表示陆地，如下所示：

.......
.##....
.##....
....##.
..####.
...###.
.......

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

由于全球变暖导致了海面上升，科学家预测未来几十年，岛屿边缘一个像素的范围会被海水淹没。

具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋)，它就会被淹没。

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

.......
.......
.......
.......
....#..
.......
.......

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

输入格式
第一行包含一个整数N。
以下 N行 N 列，包含一个由字符”#”和”.”构成的 N×N字符矩阵，代表一张海域照片，”#”表示陆地，”.”表示海洋。照片保证第 1行、第 1 列、第 N行、第N列的像素都是海洋。

输出格式
一个整数表示答案。
数据范围

1≤N≤1000

样例

输入样例1：

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

输出样例1：

1

输入样例2：

9
.........
.##.##...
.#####...
.##.##...
.........
.##.#....
.#.###...
.#..#....
.........

输出样例2：

1

遍历所有未遍历过的陆地，通过bfs/dfs计算出当前位置连通陆地的数量total，以及被淹没陆地的数量bound,若total == bound表示完整淹没的一个岛屿

bfs:

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <cstring>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII; 
int n;
queue<PII> q;
char mapp[1005][1005]; 
int fx[5]={0,0,1,-1},fy[5]={1,-1,0,0};
bool st[1005][1005];//标记该点是否已经走过，这个题走过后没有标记为‘.’，因为这个题解得过程中用到了‘.’海洋判断是否陆地是否在边界，所以来个数组标记一下是否走过就OK了 
void bfs(int x,int y,int &total,int &bound){//要用‘&’，值要带回去 
    q.push({x,y});
    st[x][y]=true;
    while(!q.empty()){
        PII t=q.front();
        total++;
        q.pop();
        bool isbound=false;
        for(int i=0;i<4;i++){//遍历此个陆地单位的上下左右四个方向 
            int a=t.x+fx[i];
            int b=t.y+fy[i];
            if(a<0||a>=n||b<0||b>=n) continue;
            if(st[a][b]) continue;
            if(mapp[a][b]=='.') {//这个陆地单位旁边有海洋 
                isbound=true;
                continue;
            }
            q.push({a,b});
            st[a][b]=true;
        }
        if(isbound){//这个陆地单位旁边有海洋，就+1 
            bound++;
        }
    }
}
int main(int argc, char** argv) {
    cin>>n;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>mapp[i][j];
        }
    }
    int total,bound,cnt=0;//total表示一个岛屿陆地的个数，bound表示这个岛屿与海洋相邻的陆地个数 
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(mapp[i][j]=='#'&&!st[i][j]){
                total=0;bound=0;
                bfs(i,j,total,bound);//一个海岛 
                if(total==bound) cnt++;
            }
        }
    }
    printf("%d\n",cnt);
        return 0;
}

dfs:

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
int n;
char mapp[1005][1005]; 
int fx[5]={0,0,1,-1},fy[5]={1,-1,0,0};
bool st[1005][1005];//标记该点是否已经走过，这个题走过后没有标记为‘.’，因为这个题解得过程中用到了‘.’海洋判断是否陆地是否在边界，所以来个数组标记一下是否走过就OK了 
void dfs(int x,int y,int &total,int &bound){//要用‘&’，值要带回去 
        st[x][y]=true;
        total++;//陆地+1 
        bool isbound=false;
        for(int i=0;i<4;i++){//遍历此个陆地单位的上下左右四个方向 
            int a=x+fx[i];
            int b=y+fy[i];
            if(mapp[a][b]=='.') {//这个陆地单位旁边有海洋 
                isbound=true;
            }
            if(!st[a][b]&&a>=0&&a<n&&b>=0&&b<n&&mapp[a][b]=='#'){
                dfs(a,b,total,bound);
            }   
        }
        if(isbound){//这个陆地单位旁边有海洋，就+1 
            bound++;
        }
    }
int main(int argc, char** argv) {
    cin>>n;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>mapp[i][j];
        }
    }
    int total,bound,cnt=0;//total表示一个岛屿陆地的个数，bound表示这个岛屿与海洋相邻的陆地个数 
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(mapp[i][j]=='#'&&!st[i][j]){
                total=0;bound=0;
                dfs(i,j,total,bound);//一个海岛 
                if(total==bound) cnt++;
            }
        }
    }
    printf("%d\n",cnt);
        return 0;
}