菜菜ccEL

用户名：uq_98515084648

访问量：2828

签　名：

等　　级
排　　名	2086
经　　验	2462
参赛次数	0
文章发表	30
年　　龄	0
在职情况	学生
学　　校
专　　业	计算机科学与技术

　　自我简介：

TA的其他文章

[编程入门]三个字符串的排序-JAVA题解
浏览：26

[编程入门]链表合并-JAVA题解
浏览：40

数据结构-链表的基本操作-JAVA实现题解
浏览：27

你可能喜欢

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

A+B for Input-Output Practice (IV) （C语言代码）

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

　　作者: 菜菜ccEL　　　　发表时间：2023-03-23 14:59:09 浏览：113　|　评论：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 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

菜菜ccEL

TA的其他文章

你可能喜欢

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

指针做法

点我有惊喜！你懂得！

A+B for Input-Output Practice (IV) （C语言代码）

妹子杀手的故事（C语言代码）

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

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.8 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

WU-拆分位数（C++代码）

字符逆序（C语言代码）

sizeof的大作用（C语言代码）

蚂蚁感冒（C语言代码）

The 3n + 1 problem （C语言代码）

蛇行矩阵（C语言代码）

【计算直线的交点数】（C语言代码）

C语言程序设计教程（第三版）课后习题10.1 （C语言代码）

菜菜ccEL

TA的其他文章

你可能喜欢

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

指针做法

点我有惊喜！你懂得！

A+B for Input-Output Practice (IV) （C语言代码）

妹子杀手的故事 （C语言代码）

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

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.8 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

WU-拆分位数 （C++代码）

字符逆序 （C语言代码）

sizeof的大作用 （C语言代码）

蚂蚁感冒 （C语言代码）

The 3n + 1 problem （C语言代码）

蛇行矩阵 （C语言代码）

【计算直线的交点数】 （C语言代码）

C语言程序设计教程（第三版）课后习题10.1 （C语言代码）

妹子杀手的故事（C语言代码）

　　评论区

WU-拆分位数（C++代码）

字符逆序（C语言代码）

sizeof的大作用（C语言代码）

蚂蚁感冒（C语言代码）

蛇行矩阵（C语言代码）

【计算直线的交点数】（C语言代码）