蓝桥杯2018年第九届真题-全球变暖-JAVA【参考优质题解】-详细注释

355 阅读 0 评论 0 点赞

原题链接：蓝桥杯2018年第九届真题-全球变暖

定义静态全局变量：
visited数组标记当前点是否被访问；
map表示地图；
dx，dy分别表示x，y进行上下左右偏移时的偏移量。

用BFS思想解题：
对**地图上每个未访问过的表示陆地的点【表示一个岛屿】进行bfs**，记录沉没的岛屿数；
在bfs中，每访问一个表示陆地的点就将其标记未已经访问，对该点上下左右四个方向查找陆地，将该岛屿整块进行标记，避免后续遍历时重复访问岛屿，在四个方向上查找陆地过程中记录当前点是否**四个方向都是陆地**，如果是，说明该岛屿不会完全沉没，返回0，如果遍历完整个岛屿都不存在**这样的点**，说明当前岛屿会完全沉没，返回1【完全沉没岛屿数+1】。
	
	import java.util.ArrayDeque;
    import java.util.Queue;
    import java.util.Scanner;
    
    public class Main {
    	static boolean[][] visited = new boolean[1010][1010];
    	static int[] dx = {-1,1,0,0};
    	static int[] dy = {0,0,-1,1};
    	static char[][] map = new char[1010][1010];
    	public static void main(String[] args) {
    		Scanner sc = new Scanner(System.in);
    		int n = sc.nextInt();
    		sc.nextLine();
    		String temp;
    		for(int i=0;i<n;i++) {
    			temp = sc.nextLine();
    			map[i] = temp.toCharArray();
    		}
    		int res = 0; // 记录结果【沉没岛屿数】
    		for(int i=0;i<n;i++) {
    			for(int j=0;j<n;j++) {
    				if(map[i][j]=='#'&&!visited[i][j]) { // 当前点为陆地且未被访问
						visited[i][j] = true; // 将其标记为已访问
    					res+=dfs(i,j); //记录结果
    				}
    			}
    		}
    		System.out.println(res);
    		
    	}
		// x,y表示当前要访问点的下标
    	public static int dfs(int x,int y) {
    		Queue<int[]> queue = new ArrayDeque<>(); // 用来装当前岛屿的点，进行逐个访问
    		int flag = 1; //标记该岛屿是否会被完全淹没【是否存在四周都是陆地的陆地】，默认会被完全淹没
			
			 // wx,wy保存队列中弹出点的坐标；
			 //tx,ty保存该点在四个方向偏移的坐标；
			 //k用来记录该点四面中是陆地的数量
    		int k = 0,tx ,ty ,wx,wy;  
    		int[] temp = null; // 保存队列中的弹出结点
    		queue.offer(new int[]{x,y}); // 先将当前要访问的结点入队
			// 遍历访问包含该点的整个岛屿【避免后续重复遍历】
    		while(!queue.isEmpty()) {
    			temp = queue.poll();
    			wx = temp[0];wy = temp[1];
    			k = 0;
				// 看上下左右是否存在陆地
    			for(int i=0;i<4;i++) {
    				tx =wx+dx[i];
    				ty =wy+dy[i];
    				if(map[tx][ty]=='#') {
    					k++; 
    					if(!visited[tx][ty]) { // 如果该点未访问
    						visited[tx][ty] = true;  
    						queue.offer(new int[] {tx,ty}); // 入队
    					}
    				}
    			}
    			if(k==4) flag = 0; //说明至少存在四面都是陆地的点，该岛屿不会被完全淹没
    		}
    		return flag;
    	}
    
    }

0.0分

1 人评分

本文分类：题解列表
浏览次数：355 次浏览
发布日期：2023-03-23 14:59:09
本文链接：https://blog.dotcpp.com/a/95186

上一篇 > 标标准准的全排列，我这里有两种去重的方式，点进来，我们细聊！
下一篇 > 翻硬币（狠狠的贪）

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

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

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

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

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

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

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

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

蓝桥杯2018年第九届真题-全球变暖-JAVA【参考优质题解】-详细注释

评论列表共有 0 条评论

发表评论取消回复

蓝桥杯2018年第九届真题-全球变暖-JAVA【参考优质题解】-详细注释

一笔画问题（dfs）

C++ ： 类和两种访问权限的练习

C++ ： 类和两种访问权限的练习

幸运儿（约瑟夫环-模拟+ Vector）

评论列表 共有 0 条评论

发表评论 取消回复

C++ ：类和两种访问权限的练习

C++ ：类和两种访问权限的练习

评论列表共有 0 条评论

发表评论取消回复