第九届蓝桥杯大赛 C语言A组 第8题 全球变暖

2023-11-23 01:00

本文主要是介绍第九届蓝桥杯大赛 C语言A组 第8题 全球变暖,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

标题:全球变暖


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

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

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

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

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

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

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

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

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

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

【样例输入】
7
.......
.##....
.##....
....##.
..####.
...###.
.......  

【样例输出】
1  


资源约定:
峰值内存消耗(含虚拟机) < 256M
CPU消耗  < 1000ms


请严格按要求输出,不要画蛇添足地打印类似:“请您输入...” 的多余内容。

注意:
main函数需要返回0;
只使用ANSI C/ANSI C++ 标准;
不要调用依赖于编译环境或操作系统的特殊函数。
所有依赖的函数必须明确地在源文件中 #include <xxx>
不能通过工程设置而省略常用头文件。

提交程序时,注意选择所期望的语言类型和编译器类型。

//-----------------------------------------题目分界线--------------------------

为了方便理解,下面的分析将相应的代码也跟在后面。  解释的太啰嗦,大佬可以直接跳过分析中的代码,最后有完整代码

分析思路:

总思路:从每一点(i, j) (0<= i,j <=N) 出发,通过深度优先遍历将与这一点相连(上下相邻,左右相邻)的部分找到,即可找到每个岛屿(每个相连的部分), 时间复杂度应该是o(n^2) = 1000^2 = 100 0000 不会超

下面代码现在只需理解//框住部分即可,从(x,y)出发,遍历上下左右,value后面会解释

void dfs(int x, int y, int value){//从 (x,y)开始 染色if(a[x][y] != 1)return;//ran sea[x][y] = value;//(x-1,y)
//if(x>0){                                           //if(a[x-1][y] == 1)dfs(x-1, y, value);       //}                                                   ////(x+1,y)                                           //if(x<n-1){                                          //if(a[x+1][y] == 1)dfs(x+1, y, value);       //}                                                   ////(x,y-1)                                           //if(y>0){                                            //if(a[x][y-1] == 1)dfs(x, y-1, value);       //}                                                   ////(x,y+1)                                           //if(y<n-1){                                          //if(a[x][y+1] == 1)dfs(x, y+1, value);       //}                                                   //
//}

其它关注点

1.数组a保存原数据,数组book根据a数组来淹没,如果(x,y)这一点上下左右都是陆地的话,(x,y)就不会被淹没,

所以将book[x][y]赋值,为了判断方便,读入时'#'存为1(有陆地),'.'存为0

void chen(int x, int y){//chen取沉没的意思,沉没过后剩下的陆地保存在book数组中bool flag = false;//是否沉没//(x-1,y)if(x>0){if(a[x-1][y] == 0)flag = true;}//(x+1,y)if(x<n-1){if(a[x+1][y] == 0)flag = true;}//(x,y-1)if(y>0){if(a[x][y-1] == 0)flag = true;}//(x,y+1)if(y<n-1){if(a[x][y+1] == 0)flag = true;}if(flag == false)book[x][y]=a[x][y];//没沉没的 标记为a[x][y] 这里a[x][y]为一个正数,后面会解释
}
        int i,j;//读入部分char ch;cin>>n;for(i=0; i<n; i++){for(j=0; j<n; j++){cin>>ch;ch == '.'?a[i][j] = 0:a[i][j] = 1;//岛屿为1 海洋为0}}

2.想到这里发现了问题,如果先沉没,再统计剩下的岛屿数的话,以下情况会出错

0 1 0 1 0

1 1 1 1 1

0 1 0 1 0

这是淹没前的岛屿,是一个岛屿

0 0 0 0 0

0 1 0 1 0

0 0 0 0 0

这是淹没后的岛屿,变成了两个,这就出现问题了,我的想法是,先沉没,再统计剩下的岛屿数s1,被淹没的岛屿数就是淹没前的岛屿数s0 - s1 ,这样,上述情况本来应该只算剩下1个岛屿,但我的方法确错误的以为剩下2个岛屿

所以我想到的解决方法是:一开始找到所有岛屿,为每个岛屿染一个独一无二的颜色(赋值为一个正整数),最后淹没后,统计剩余的颜色数即可获得剩余岛屿数。

这个代码又出现了。。。value即为要染的颜色 ,判断a[x][y]是不是1,是1说明这里是岛屿,而且还没被染过色(染色从10开始)

void dfs(int x, int y, int value){if(a[x][y] != 1)return;//不是1说明这里是海洋,或者被染过色了,跳过//染色a[x][y] = value;//(x-1,y)if(x>0){if(a[x-1][y] == 1)dfs(x-1, y, value);}//(x+1,y)if(x<n-1){if(a[x+1][y] == 1)dfs(x+1, y, value);}//(x,y-1)if(y>0){if(a[x][y-1] == 1)dfs(x, y-1, value);}//(x,y+1)if(y<n-1){if(a[x][y+1] == 1)dfs(x, y+1, value);}
}

主函数调用部分

        int color = 10;for(i=0; i<n; i++){for(j=0; j<n; j++){if(a[i][j] == 1){dfs(i,j,color++);//每个岛屿染不同颜色,颜色从10开始}}}

3.最后统计完没被淹没的岛屿后,用最开始的岛屿数减去即可。。。然而我考试的时候忘了减OTZ

开始的岛屿数可以由color获得:  color-10


//------------------------------------分析部分结束-----------------------------------------------------------

以下为完整代码

#include<iostream>using namespace std;const int MAX_N = 1005;
int a[MAX_N][MAX_N];
int book[MAX_N][MAX_N];
int v[MAX_N];
int res;
int n;void dfs(int x, int y, int value){//从 (x,y)开始if(a[x][y] != 1)return;//染色a[x][y] = value;//(x-1,y)if(x>0){if(a[x-1][y] == 1)dfs(x-1, y, value);}//(x+1,y)if(x<n-1){if(a[x+1][y] == 1)dfs(x+1, y, value);}//(x,y-1)if(y>0){if(a[x][y-1] == 1)dfs(x, y-1, value);}//(x,y+1)if(y<n-1){if(a[x][y+1] == 1)dfs(x, y+1, value);}
}
//-------------------------------
void chen(int x, int y){bool flag = false;//是否沉没if(x>0){if(a[x-1][y] == 0)flag = true;}//(x+1,y)if(x<n-1){if(a[x+1][y] == 0)flag = true;}//(x,y-1)if(y>0){if(a[x][y-1] == 0)flag = true;}//(x,y+1)if(y<n-1){if(a[x][y+1] == 0)flag = true;}if(flag == false)book[x][y]=a[x][y];//没沉没的,将这块的颜色记录在book中
}
//----------------------------------无用函数开始
void print(){for(int i=0; i<n; i++){for(int j=0; j<n; j++){cout<<a[i][j]<<" ";}cout<<endl;}
}
void print2(){for(int i=0; i<n; i++){for(int j=0; j<n; j++){cout<<book[i][j]<<" ";}cout<<endl;}
}
//-----------------------------------------------无用函数结束
int main(){int i,j;char ch;cin>>n;for(i=0; i<n; i++){for(j=0; j<n; j++){cin>>ch;ch == '.'?a[i][j] = 0:a[i][j] = 1;}}//染色int color = 10;for(i=0; i<n; i++){for(j=0; j<n; j++){if(a[i][j] == 1){dfs(i,j,color++);}}}cout<<"染色后:"<<endl;print();cout<<endl;//这里是多余的  看一下染色后的结果//沉没for(i=0; i<n; i++){for(j=0; j<n; j++){if(a[i][j] != 0){//如果这里是岛屿 再判断是否沉没chen(i,j);}}}cout<<"沉没后:"<<endl;print2();cout<<endl;//这里是多余的  看一下沉没后的结果for(i=0; i<n; i++){for(j=0; j<n; j++){if(book[i][j] != 0){//如果这里记录了没沉没的岛屿v[ book[i][j] ]++;//将该颜色值+1}}}for(i=0; i<MAX_N; i++){//数数共剩下多少个颜色if(v[i] != 0){res++;}}int qian = color - 10;cout<<qian - res;return 0;
}

结果截图



PS:第一篇自己很用心写的答案,感谢大家的阅读,有不足之处还望指出,Thanks♪(・ω・)ノ

写于2018/04/05

这篇关于第九届蓝桥杯大赛 C语言A组 第8题 全球变暖的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/414190

相关文章

高效+灵活,万博智云全球发布AWS无代理跨云容灾方案!

摘要 近日,万博智云推出了基于AWS的无代理跨云容灾解决方案,并与拉丁美洲,中东,亚洲的合作伙伴面向全球开展了联合发布。这一方案以AWS应用环境为基础,将HyperBDR平台的高效、灵活和成本效益优势与无代理功能相结合,为全球企业带来实现了更便捷、经济的数据保护。 一、全球联合发布 9月2日,万博智云CEO Michael Wong在线上平台发布AWS无代理跨云容灾解决方案的阐述视频,介绍了

科研绘图系列:R语言扩展物种堆积图(Extended Stacked Barplot)

介绍 R语言的扩展物种堆积图是一种数据可视化工具,它不仅展示了物种的堆积结果,还整合了不同样本分组之间的差异性分析结果。这种图形表示方法能够直观地比较不同物种在各个分组中的显著性差异,为研究者提供了一种有效的数据解读方式。 加载R包 knitr::opts_chunk$set(warning = F, message = F)library(tidyverse)library(phyl

透彻!驯服大型语言模型(LLMs)的五种方法,及具体方法选择思路

引言 随着时间的发展,大型语言模型不再停留在演示阶段而是逐步面向生产系统的应用,随着人们期望的不断增加,目标也发生了巨大的变化。在短短的几个月的时间里,人们对大模型的认识已经从对其zero-shot能力感到惊讶,转变为考虑改进模型质量、提高模型可用性。 「大语言模型(LLMs)其实就是利用高容量的模型架构(例如Transformer)对海量的、多种多样的数据分布进行建模得到,它包含了大量的先验

C语言 | Leetcode C语言题解之第393题UTF-8编码验证

题目: 题解: static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num & MASK1) == 0) {return

MiniGPT-3D, 首个高效的3D点云大语言模型,仅需一张RTX3090显卡,训练一天时间,已开源

项目主页:https://tangyuan96.github.io/minigpt_3d_project_page/ 代码:https://github.com/TangYuan96/MiniGPT-3D 论文:https://arxiv.org/pdf/2405.01413 MiniGPT-3D在多个任务上取得了SoTA,被ACM MM2024接收,只拥有47.8M的可训练参数,在一张RTX

如何确定 Go 语言中 HTTP 连接池的最佳参数?

确定 Go 语言中 HTTP 连接池的最佳参数可以通过以下几种方式: 一、分析应用场景和需求 并发请求量: 确定应用程序在特定时间段内可能同时发起的 HTTP 请求数量。如果并发请求量很高,需要设置较大的连接池参数以满足需求。例如,对于一个高并发的 Web 服务,可能同时有数百个请求在处理,此时需要较大的连接池大小。可以通过压力测试工具模拟高并发场景,观察系统在不同并发请求下的性能表现,从而

C语言:柔性数组

数组定义 柔性数组 err int arr[0] = {0}; // ERROR 柔性数组 // 常见struct Test{int len;char arr[1024];} // 柔性数组struct Test{int len;char arr[0];}struct Test *t;t = malloc(sizeof(Test) + 11);strcpy(t->arr,

C语言指针入门 《C语言非常道》

C语言指针入门 《C语言非常道》 作为一个程序员,我接触 C 语言有十年了。有的朋友让我推荐 C 语言的参考书,我不敢乱推荐,尤其是国内作者写的书,往往七拼八凑,漏洞百出。 但是,李忠老师的《C语言非常道》值得一读。对了,李老师有个官网,网址是: 李忠老师官网 最棒的是,有配套的教学视频,可以试看。 试看点这里 接下来言归正传,讲解指针。以下内容很多都参考了李忠老师的《C语言非

C 语言基础之数组

文章目录 什么是数组数组变量的声明多维数组 什么是数组 数组,顾名思义,就是一组数。 假如班上有 30 个同学,让你编程统计每个人的分数,求最高分、最低分、平均分等。如果不知道数组,你只能这样写代码: int ZhangSan_score = 95;int LiSi_score = 90;......int LiuDong_score = 100;int Zhou

C 语言的基本数据类型

C 语言的基本数据类型 注:本文面向 C 语言初学者,如果你是熟手,那就不用看了。 有人问我,char、short、int、long、float、double 等这些关键字到底是什么意思,如果说他们是数据类型的话,那么为啥有这么多数据类型呢? 如果写了一句: int a; 那么执行的时候在内存中会有什么变化呢? 橡皮泥大家都玩过吧,一般你买橡皮泥的时候,店家会赠送一些模板。 上