乔梦圆


私信TA

用户名:1430186623

访问量:902

签 名:

等  级
排  名 11016
经  验 980
参赛次数 0
文章发表 2
年  龄 0
在职情况 学生
学  校 山西大同大学
专  业

  自我简介:

解题思路:


题目问的是最终有多少个岛屿会被淹没,而题目又告诉我们:

**如果一块陆地四周都是海,则这块陆地会被淹没。**
我们可以这样理解:

**如果这块岛屿中存在一个点四周都是陆地‘#’,则这个岛屿一定不会被淹没。**
转换成这个思想之后问题就好解决了

        刚开始还是之前的联通块套路,**dfs搜索连在一块的岛屿并标记,每搜索一次证明存在的岛屿数+1,在搜索的过程中我们需要看看是否存在这样的点(四周都是‘#’),如果存在,我们就把flag置为0,不存在置为1,然后每搜索完一大块岛屿之后答案数+flag就可以了。**



参考代码:

#include <iostream>
#include <stdio.h>
using namespace std;
char a[1001][1001],book[1001][1001];//a存储地图  book为标记数组  
int next1[4][2]={{0,1},{0,-1},{1,0},{-1,0}};//枚举下一步搜索操作
int N,flag,ans=0;//flag为标志变量 如果存在四周都是#的点 标记为0 如果不存在 标记为1 
void dfs(int x,int y) //搜索岛屿 
{ int i,tx,ty;
  for(i=0;i<4;i++)
   { tx=x+next1[i][0];
     ty=y+next1[i][1];
     if(tx<1||ty<1||ty>N||tx>N) continue;//边界情况处理 
     if(!book[tx][ty]&&a[tx][ty]=='#')
     { book[tx][ty]=1; //标记这个点 
        if(flag&&tx+1>=1&&ty+1>=1&&tx+1<=N&&ty+1<=N&&a[tx][ty+1]=='#'&&a[tx][ty-1]=='#'&&a[tx+1][ty]=='#'&&a[tx-1][ty]=='#')
        flag=0; //如果存在四周都是#的点,证明这个岛屿不会被淹没 
       dfs(tx,ty);
     }
   }
}
int main()
{  
    cin>>N;
    int i,j;
    for(i=1;i<=N;i++)
        for(j=1;j<=N;j++)
         cin>>a[i][j];//输入地图 
    for(i=1;i<=N;i++)
     for(j=1;j<=N;j++)
     { if(a[i][j]=='#'&&!book[i][j])//开始从这个点搜索这个岛屿 
       { book[i][j]=1;
         flag=1;//先默认不存在四周都是#这样的点 
         dfs(i,j);
         ans+=flag;//如果搜索完成后还是不存在,则这个岛屿一定会淹没,加到结果里 
       }
     }
     printf("%d",ans);
    return 0;
}


 

0.0分

8 人评分

  评论区

判断四周是否都是‘*’的时候不能用if直接判断,因为有可能靠近边缘三面都是‘*’一面是边界。
2022-03-28 00:48:01
请问这个是怎样实现相加的呀?tx=x+next1[i][0];???????????
2022-02-09 23:38:01
  • «
  • 1
  • »