标题:全球变暖


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


……. 

.##…. 

.##…. 

….##. 

..####. 

…###. 

…….


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


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


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


……. 

……. 

……. 

……. 

….#.. 

……. 

…….


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


【输入格式】 

第一行包含一个整数N。 (1 <= N <= 1000) 

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


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


【输出格式】 

一个整数表示答案。


【输入样例】 

……. 

.##…. 

.##…. 

….##. 

..####. 

…###. 

…….


【输出样例】 

1


【输入样例】 

10 

………. 

.###..###. 

.###..###. 

.########. 

………. 

.###…#.. 

.#.#…#.. 

.###…… 

………. 

………. 

【输出样例】 

资源约定: 

峰值内存消耗(含虚拟机) < 256M 

CPU消耗 < 1000ms





思路: 岛屿最后不得被淹没 即 四个方向有岛屿存在 对本岛屿有贡献 为岛屿时 # 将 岛屿坐标 记录为 +4 对应四个方向对应记录贡献+ 1 输入完毕 找值为 8的 点即可


第一次 找寻 zx()搜索 查找 有多少岛屿 

第二次 找寻 zx2() 搜索 还剩几个岛 找到一个岛(不管这个大岛最后有多少小岛出来) 都全部融掉 (防止 一个岛融成多个岛 重复计算)

 原文   欢迎访问 我的博客


#include <stdio.h>
#include <string.h> 
char s[1002][1002];
 void zx(long int x,long int y)
 {
    if(s[x][y]!='#')return;
    s[x][y]='4';
    zx(x+1,y);
    zx(x-1,y);
    zx(x,y-1);
    zx(x,y+1);
 }
 void zx2(long int x,long int y)
 { 
    if(s[x][y]>='4'&&s[x][y]<='9')//为岛屿则全部淹没(不管这个大岛最后有多少小岛出来)
    {
    s[x][y]='.';
    zx2(x+1,y);
    zx2(x-1,y);
    zx2(x,y-1);
    zx2(x,y+1);
    }
     return;
 }
 int main()
 {long int i,n,j,ans=0,sum=0;
 scanf("%ld",&n);
  for(i=1;i<=n;i++)
  for(j=1;j<=n;j++)
  {
    while(1)
    {
     scanf("%c",&s[i][j]);
     if(s[i][j]=='.'||s[i][j]=='#')break;
     }
    }
  for(i=1;i<=n;i++)//找寻多少块岛屿;
  for(j=1;j<=n;j++)
   if(s[i][j]=='#')
     { 
      zx(i,j); //将同一块岛屿 标记防重复 
      ans++;} 
      
  for(i=1;i<=n;i++)//找寻那些块岛屿不会被淹;
  for(j=1;j<=n;j++)
     if(s[i][j]>='4'&&s[i][j]<='9')
     {  s[i-1][j]+=1;
         s[i+1][j]+=1;
         s[i][j-1]+=1;
         s[i][j+1]+=1;
     }
  for(i=1;i<=n;i++)s[1][i]++,s[n][i]++,s[i][1]++,s[i][n]++;//处理边界
  for(i=1;i<=n;i++)//找寻剩多少块岛屿;
  for(j=1;j<=n;j++) 
     if(s[i][j]=='8')
     { 
      zx2(i,j); //将同一块岛屿 标记防重复 
      sum++;} 
 printf("%ld\n",ans-sum);
 return 0;
 }


点赞(29)
 

0.0分

1 人评分

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:

一点编程也不会写的:零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码?手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的 必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

评论列表 共有 11 条评论

mirage 5年前 回复TA
@mirage 。。。。看错题了
mirage 5年前 回复TA
8
........
.##..##.
.######.
.##..##.
........
........
........
........

这个为啥是 0 ?
C语言一菜鸟级 5年前 回复TA
@Troc 那么说那 我确实 貌似没考虑边界的贡献 , 感谢你的更正
Troc 5年前 回复TA
这个代码有点错误吧!下面这个例子我认为正确答案应该是2,但是代码测试数据结果为3
5
##...
...##
#....
##...
##...
下一站幸福 6年前 回复TA
@下一站幸福 @LHL thank for you,i know
C语言一菜鸟级 6年前 回复TA
@下一站幸福 @xiayizhanxingfu 蓝桥杯是  提交上去 不会反馈任何信息  可以多次提交 以最后一次为准
C语言一菜鸟级 6年前 回复TA
@下一站幸福 蓝桥杯是 以提交最后一次的答案为准  你交上去 无法知道 对或者错  你最多在本地测试一下,对了 觉得没问题就交
下一站幸福 6年前 回复TA
@下一站幸福 @LHL 我没参加过蓝桥杯,想问问,蓝桥杯比赛是不是提交答案就能知道结果正确吗
下一站幸福 6年前 回复TA
@下一站幸福 我没参加过蓝桥杯,想问问,蓝桥杯比赛是不是提交答案就能知道结果正确吗
C语言一菜鸟级 6年前 回复TA
@下一站幸福 菜鸡一个  还想再试一试