2018年蓝桥杯JAVA B组“全球变暖”题目详解

2023-11-23 01:00

本文主要是介绍2018年蓝桥杯JAVA B组“全球变暖”题目详解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

对2018年蓝桥杯JAVA B组“全球变暖”题目详解

题目

标题:全球变暖
你有一张某海域NxN像素的照片,".“表示海洋、”#"表示陆地,如下所示:
……..##.....##........##...####....###.…….
其中"上下左右"四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有2座岛屿。
由于全球变暖导致了海面上升,科学家预测未来几十年,岛屿边缘一个像素的范围会被海水淹没。具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋),它就会被淹没。
例如上图中的海域未来会变成如下样子:
…….…….…….…….....#..…….…….
请你计算:依照科学家的预测,照片中有多少岛屿会被完全淹没。
【输入格式】
第一行包含一个整数N。 (1 <= N <= 1000)
以下N行N列代表一张海域照片。
照片保证第1行、第1列、第N行、第N列的像素都是海洋。
【输出格式】
一个整数表示答案。
【输入样例】
7![……..##.....##........##...####....###.…….](https://img-blog.csdnimg.cn/20190301160529511.png)
【输出样例】
1
资源约定:
峰值内存消耗(含虚拟机) < 256M
CPU消耗 < 1000ms
请严格按要求输出,不要画蛇添足地打印类似:“请您输入…” 的多余内容。
所有代码放在同一个源文件中,调试通过后,拷贝提交该源码。
不要使用package语句。不要使用jdk1.7及以上版本的特性。
主类的名字必须是:Main,否则按无效代码处理。

思路:
1.由于二维字符矩阵不能直接存入char[][]矩阵中,所以使用String[i]间接存储,i为行数,String[i]记录第i+1行的字符序列,之后再通过String的toCharArray()方法将每行字符序列转换为char数组,这样就利用char[][]存储了二维字符序列。
注明:采用char[][]进行存储要优于String[]存储,因为后续需进行遍历操作,而使用String中的charAt()方法虽然也可达到相同效果,但效率相比于char[][]来说效率要差很多。
2.二维矩阵存储后,首先要统计未发生淹没过程时的岛屿数。首先两个for循环遍历矩阵每个字符,如果这个字符是陆地(’#’)且未曾访问过,则岛屿数+1,之后从该字符处进行深度搜索,目的将与该字符相连的所有陆地标记为已访问(同属于同一个岛屿)。
3.对于dfs方法中,首先需判断i,j是否超出矩阵边界,避免下标越界情况出现。之后将该字符处的访问标志为置1表示已访问过,然后依次判断该字符上右下左四个方向是否存在陆地且未曾访问过,如果存在则把找到的符合条件的字符作为当前字符,继续深搜,这样属于同一个岛屿的陆地访问标志都变成了1,且岛屿数只加过1次。
4.进行淹没过程。同样使用两个for循环逐个字符判断,如果陆地的上下左右四个方向中某个方向存在海洋,则该陆地将变为海洋。这里需注意,要避免前面的陆地变成海洋带来的影响,为了便于说明,举个例子,如下图所示。

淹没前
......
..###.
..###.
.####.
......正确淹没后
......      
......
...#..
......
......错误淹没后
......      
......
......
......
......

如果不考虑相互之间的影响,仅考虑上下左右四个方向是否存在海洋,存在就直接将陆地改为海洋,则会导致上图中的错误淹没后结果,因为前一个陆地淹没后,对于下一个要判断的相邻陆地来说,由于前一个陆地已经变为海洋,对于要判断的陆地的某个方向肯定存在海洋了,则该判断陆地将直接变为海洋,这很明显是错误的。为了避免前一个陆地修改后影响下一个陆地的判断,引入修改位vis[][]。
5.淹没过程结束后,再次使用dfs方法计算淹没后剩余的岛屿数,淹没前岛屿数与淹没后岛屿数相减,即消失的岛屿数。

详细代码如下:

import java.util.Scanner;public class Main {static int N;static int[][] dfs_vis;//dfs深度搜索  检查当前点上右下左四个方向是否同时满足陆地、未访问两个条件//满足条件就以该点为下一个检查点进行判读,同时将访问标志设为1static void dfs(char[][] a,int i,int j){if(i>=1&&i<N-1&&j<N-1&&j>=1){//访问标志设为1dfs_vis[i][j]=1;//上if(a[i-1][j]=='#'&&dfs_vis[i-1][j]==0){dfs(a,i-1,j);}//右if(i>=1&&j<N-1&&a[i][j+1]=='#'&&dfs_vis[i][j+1]==0){dfs(a,i,j+1);}//下if(i>=1&&j<N-1&&a[i+1][j]=='#'&&dfs_vis[i+1][j]==0){dfs(a,i+1,j);}//左if(i>=1&&j<N-1&&a[i][j-1]=='#'&&dfs_vis[i][j-1]==0){dfs(a,i,j-1);}}}public static void main(String[] args){Scanner scan=new Scanner(System.in);N=scan.nextInt();String[] s=new String[N];char[][] c=new char[N][N];dfs_vis=new int[N][N];for(int i=0;i<N;i++){s[i]=scan.next();}scan.close();int[][] vis=new int[N][N];for(int i=0;i<N;i++){c[i]=s[i].toCharArray();		}//未淹没岛屿数int pre_sum=0;for(int i=1;i<N-1;i++){for(int j=1;j<N-1;j++){if(c[i][j]=='#'&&dfs_vis[i][j]==0){dfs(c,i,j);pre_sum++;}}}//System.out.println(pre_sum);//淹没过程for(int i=1;i<N-1;i++){for(int j=1;j<N-1;j++){if(c[i][j]=='#'){if((c[i-1][j]=='.'&&vis[i-1][j]==0)||(c[i+1][j]=='.'&&vis[i+1][j]==0)||(c[i][j-1]=='.'&&vis[i][j-1]==0)||(c[i][j+1]=='.'&&vis[i][j+1]==0)){c[i][j]='.';vis[i][j]=1;}}}}//打印淹没后结果/*for(int i=0;i<N;i++){for(int j=0;j<N;j++){System.out.print(c[i][j]);}System.out.println();}*///淹没后岛屿数dfs_vis=new int[N][N];int now_sum=0;for(int i=1;i<N-1;i++){for(int j=1;j<N-1;j++){if(c[i][j]=='#'&&dfs_vis[i][j]==0){dfs(c,i,j);now_sum++;}}}//System.out.println(now_sum);//两者之差就是淹没的岛屿数System.out.println(pre_sum-now_sum);}
}

附一组测试用例

8
........
..####..
.####.#.
..##....
....#.#.
.#.###..
...###..
........

用了多组测试用例测试,结果都对了,但不知道是否还存在疏漏的地方,如果大家发现不对的地方,欢迎评论指正,我会第一时间改掉,免得误导别人……

这篇关于2018年蓝桥杯JAVA B组“全球变暖”题目详解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:https://blog.csdn.net/qq_41176515/article/details/90115791
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/414193

相关文章

Java中Arrays类和Collections类常用方法示例详解

《Java中Arrays类和Collections类常用方法示例详解》本文总结了Java中Arrays和Collections类的常用方法,涵盖数组填充、排序、搜索、复制、列表转换等操作,帮助开发者高... 目录Arrays.fill()相关用法Arrays.toString()Arrays.sort()A

Spring Boot Maven 插件如何构建可执行 JAR 的核心配置

《SpringBootMaven插件如何构建可执行JAR的核心配置》SpringBoot核心Maven插件,用于生成可执行JAR/WAR,内置服务器简化部署,支持热部署、多环境配置及依赖管理... 目录前言一、插件的核心功能与目标1.1 插件的定位1.2 插件的 Goals(目标)1.3 插件定位1.4 核

如何使用Lombok进行spring 注入

《如何使用Lombok进行spring注入》本文介绍如何用Lombok简化Spring注入,推荐优先使用setter注入,通过注解自动生成getter/setter及构造器,减少冗余代码,提升开发效... Lombok为了开发环境简化代码,好处不用多说。spring 注入方式为2种,构造器注入和setter

使用zip4j实现Java中的ZIP文件加密压缩的操作方法

《使用zip4j实现Java中的ZIP文件加密压缩的操作方法》本文介绍如何通过Maven集成zip4j1.3.2库创建带密码保护的ZIP文件,涵盖依赖配置、代码示例及加密原理,确保数据安全性,感兴趣的... 目录1. zip4j库介绍和版本1.1 zip4j库概述1.2 zip4j的版本演变1.3 zip4

Python 字典 (Dictionary)使用详解

《Python字典(Dictionary)使用详解》字典是python中最重要,最常用的数据结构之一,它提供了高效的键值对存储和查找能力,:本文主要介绍Python字典(Dictionary)... 目录字典1.基本特性2.创建字典3.访问元素4.修改字典5.删除元素6.字典遍历7.字典的高级特性默认字典

Java堆转储文件之1.6G大文件处理完整指南

《Java堆转储文件之1.6G大文件处理完整指南》堆转储文件是优化、分析内存消耗的重要工具,:本文主要介绍Java堆转储文件之1.6G大文件处理的相关资料,文中通过代码介绍的非常详细,需要的朋友可... 目录前言文件为什么这么大?如何处理这个文件?分析文件内容(推荐)删除文件(如果不需要)查看错误来源如何避

SpringBoot整合Dubbo+ZK注册失败的坑及解决

《SpringBoot整合Dubbo+ZK注册失败的坑及解决》使用Dubbo框架时,需在公共pom添加依赖,启动类加@EnableDubbo,实现类用@DubboService替代@Service,配... 目录1.先看下公共的pom(maven创建的pom工程)2.启动类上加@EnableDubbo3.实

SpringBoot整合(ES)ElasticSearch7.8实践

《SpringBoot整合(ES)ElasticSearch7.8实践》本文详细介绍了SpringBoot整合ElasticSearch7.8的教程,涵盖依赖添加、客户端初始化、索引创建与获取、批量插... 目录SpringBoot整合ElasticSearch7.8添加依赖初始化创建SpringBoot项

JAVA覆盖和重写的区别及说明

《JAVA覆盖和重写的区别及说明》非静态方法的覆盖即重写,具有多态性;静态方法无法被覆盖,但可被重写(仅通过类名调用),二者区别在于绑定时机与引用类型关联性... 目录Java覆盖和重写的区别经常听到两种话认真读完上面两份代码JAVA覆盖和重写的区别经常听到两种话1.覆盖=重写。2.静态方法可andro

MySQL 主从复制部署及验证(示例详解)

《MySQL主从复制部署及验证(示例详解)》本文介绍MySQL主从复制部署步骤及学校管理数据库创建脚本,包含表结构设计、示例数据插入和查询语句,用于验证主从同步功能,感兴趣的朋友一起看看吧... 目录mysql 主从复制部署指南部署步骤1.环境准备2. 主服务器配置3. 创建复制用户4. 获取主服务器状态5