题目描述


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

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

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

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

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

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

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

【输入格式】
第一行包含一个整数N。  (1 <= N <= 1000)  
以下N行N列代表一张海域照片。  

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

【输出格式】
一个整数表示答案。

【样例输入】

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

【样例输出】
1  

解题思路:


bfs:

对于#:vis[][]=0,表示未访问,vis[][]=1,表示已访问且该位置是临海的,vis[][]=2表示已访问且该位置不临海

对于#,都初始化其vis[][]=2,如果后续它符合临海的条件,再令vis[][]=1

第一次bfs确定vis数组,统计有多少个岛屿,然后把vis[][]=1的位置换成.   表示淹没

第二次bfs统计淹没后还剩余多少岛屿

做差即结果

dfs:

对于#,判断其四周是否都是#,如果是的话不临海#计数器ans++,标志flag为true,一个岛屿中只需要知道有一个不临海的#就可以了,flag避免了重复计算同一个岛屿中不临海#的数量,造成结果错误。

dfs的同时,res_ans统计有多少岛屿

做差即结果

 

ac代码:


bfs

#include <iostream>
#include <cmath>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <sstream>
#define maxn 1002
using namespace std;
typedef long long ll;
struct node{
    int x,y;
    node(int x=-1,int y=-1):x(x),y(y){}
};
int vis[maxn][maxn]={0};
char a[maxn][maxn];
int n,ans=0;
queue<node> q;
int X[4]={0,-1,0,1};//x
int Y[4]={1,0,-1,0};//y 右,上,左,下
bool check(int x,int y)
{
    for(int i=0;i<4;i++)
    {
        int c=x+X[i],r=y+Y[i];
        if(c>=0&&c<n&&r>=0&&r<n&&a[c][r]=='.')
            return true;
    }
    return false;
}
void bfs()
{
    while(!q.empty())
    {
        node s=q.front();q.pop();
        if(check(s.x,s.y))
            vis[s.x][s.y]=1;//四个方位有方位临水
        for(int i=0;i<4;i++)
        {
            int c=s.x+X[i],r=s.y+Y[i];
            if(c>=0&&c<n&&r>=0&&r<n&&a[c][r]=='#'&&vis[c][r]==0)//不越界且是#且不是已经访问过的
            {
                vis[c][r]=2;//先把当前#四周的#的vis都设为2,此后满足check()则vis变成1,否则还是2
                q.push(node(c,r));
            }
        }
    }
}
int main()
{
    //freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%s",a[i]);
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(a[i][j]=='#'&&vis[i][j]==0)
            {
                q.push(node(i,j));
                ans++;
                bfs();
            }
        }
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(vis[i][j]==1&&a[i][j]=='#')
                a[i][j]='.';
        }
    }
    int sum=0;//求最后还剩下多少岛屿
    memset(vis,0,sizeof(vis));
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(a[i][j]=='#'&&vis[i][j]==0)
            {
                q.push(node(i,j));
                sum++;
                bfs();
            }
        }
    }
    printf("%d",ans-sum);
    return 0;
}

dfs:来源大佬https://blog.csdn.net/memeda1141

#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<stdio.h>
using namespace std;
bool flag;//标记是否岛屿沉没
char a[1010][1010];//地图保存
int cnt=0;//统计周围#的数目
int n;//
int d[4][2]= {1,0,-1,0,0,1,0,-1};//枚举方向的数组
int ans=0;//被淹没后的岛屿个数
int res_ans=0;//没被淹没的岛屿的个数
void dfs(int x,int y)//回溯
{
	if(a[x][y]!='#')//如果这个点被标记成已经探索的岛屿内容或者是海洋,那么就返回
		return ;
	if(x>=n||x<0||y>=n||y<0)//如果越界了也是返回
		return ;
	if(flag==false)//如果还没确定不会被淹没,即当前是被淹没状态
	{cnt=0;//统计这个岛屿的当前点坐标x,y的上下左右的四个点是不是都是'#',如果确实是这样的,那么为我们就可以确定这个岛屿不会被淹没,我们姑且叫这样的点叫做不可淹没点,,那么只要一个岛屿有一个这样的点就一定不会被淹没
		for(int i=0; i<4; i++)//枚举四个方向
		{
			int tx=x+d[i][0];
			int ty=y+d[i][1];
			if(tx<n&&tx>=0&&ty<n&&ty>=0&&a[tx][ty]!='.')//假设枚举的四周的点不会超界并且不是海洋,那么cnt数目+1
			{
				cnt++;
			}
		}
		if(cnt==4)//如果四周的点都是这样的那么这个点就是不可淹没点
		{
			ans++;//最后不会被淹没的点+!
			flag=true;//这个岛屿标记已经确定,当前岛屿是不可以被淹没的,所以当回溯这个岛屿其他点的时候就不用再来检查了,因为一个岛屿有一个这样的不可淹没点就够了
		}
	}
	a[x][y]='*';//对于已经探索的岛屿的内容标记成'*',
	for(int i=0; i<4; i++)
	{
		int tx=x+d[i][0];
		int ty=y+d[i][1];
			dfs(tx,ty);//对于四个方向进行回溯岛屿的所有点
	}
}
int main()
{
	cin>>n;
	for(int i=0; i<n; i++)
	{
		scanf("%s",a[i]);
	}//输入数据
	for(int i=0; i<n; i++)
	{
		for(int j=0; j<n; j++)
		{//遍历地图的所以坐标
			if(a[i][j]=='#')//如果被找到的是同一个岛屿那么会被标记成'*',不会进入回溯,只有是'#'才说明是未被搜索的岛屿的一角
			{
				res_ans++;//那么岛屿数目加1
				flag=false;//假设会淹没
				dfs(i,j);//回溯标记这个岛屿的所有点的坐标,并且如果不会被完全的淹没,那么就标记
			}
		}
	}
	cout<<res_ans-ans<<endl;//输出答案
}