第九届蓝桥杯全球变暖java

超！级！容易！理解的深度优先搜索！

题目：
你有一张某海域NxN像素的照片，".“表示海洋、”#"表示陆地，如下所示：

…
.##…
.##…
…##.
…####.
…###.
…

其中"上下左右"四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有2座岛屿。
由于全球变暖导致了海面上升，科学家预测未来几十年，岛屿边缘一个像素的范围会被海水淹没。具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋)，它就会被淹没。
例如上图中的海域未来会变成如下样子：

…
…
…
…
…#…
…
…

请你计算：依照科学家的预测，照片中有多少岛屿会被完全淹没。
【输入格式】
第一行包含一个整数N。 (1 <= N <= 1000)
以下N行N列代表一张海域照片。
照片保证第1行、第1列、第N行、第N列的像素都是海洋。
【输出格式】
一个整数表示答案。
【输入样例】
7
…
.##…
.##…
…##.
…####.
…###.
…

【输出样例】
1
资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗 < 1000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入…” 的多余内容。
所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
不要使用package语句。不要使用jdk1.7及以上版本的特性。
主类的名字必须是：Main，否则按无效代码处理。

解题思路：
1、第一步：首先需要计算海平面上升之前该海域有多少个岛屿。由题意可得"#“表示陆地，其中"上下左右"四个方向上连在一起的一片陆地组成一座岛屿。可以利用DFS解题。
DFS解题思路：从任意”#“开始，不停地把邻接的部分用”.“代替。1次DFS后与初始的这个”#“连接的所有”#“就都被替换成了”.",因此知道图中不再存在"#“为止，总共进行的DFS次数就是答案了。题目*有"上下左右"四个方向。
2、第二步：查看海平面上升之后哪些陆地会被淹没。
解题思路：遍历整个海域，如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋)，它就会被淹没，则将该陆地替换为”*"表示该陆地已经被淹没。
3、第三步：计算海平面上升之后还有多少个岛屿。其解题思路与第一步类似。
4、第四步：用海平面上升之前海域的岛屿数减去海平面上升之后海域的岛屿数，即可得到海平面上升之后海域中有多少岛屿被完全淹没的数目。

代码：
代码略长，但是很容易理解哦！

public class Demo9 {
	static int N;//海域的大小
	
	public static void fun(String[][] field1,int x,int y) {
		for(int dx=-1;dx<=1;dx++) {
			for(int dy=-1;dy<=1;dy++) {
				if(((dx==0)&&(dy==-1))||((dx==0)&&(dy==1))||((dx==-1)&&(dy==0))||((dx==1)&&(dy==0))) {
					int nx=x+dx,ny=y+dy;
					//若陆地上下左右四个方向与海洋相邻，则将该陆地"#"替换为"*",表示该陆地已经被淹没
					if(0<=nx&&nx<N&&0<=ny&&ny<N&&field1[nx][ny].equals("#")) {
						field1[nx][ny]="*";
					}
				}
			}
		}
	}
	
	public static void dfs(String[][] field,int x,int y) {
		field[x][y]=".";//将现在的位置变为".",即"#"变为"."
		for(int dx=-1;dx<=1;dx++) {
			for(int dy=-1;dy<=1;dy++) {
				//“上下左右”四个方向移动
				if(((dx==0)&&(dy==-1))||((dx==0)&&(dy==1))||((dx==-1)&&(dy==0))||((dx==1)&&(dy==0))) {
					int nx=x+dx,ny=y+dy;
					//若移动后的点在海域内并且上下左右四个方向上仍有陆地，继续DFS
					if(0<=nx&&nx<N&&0<=ny&&ny<N&&field[nx][ny].equals("#")) {
						dfs(field,nx,ny);
					}
				}
			}
		}
	}
	
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		N=sc.nextInt();//输入海域的大小
		String[][] field=new String[N][N];//field用于计算海平面上升之前海域中的岛屿数
		String[][] field1=new String[N][N];//field1用于模拟海平面上升及计算海平面上升之后海域中的岛屿数
		//输入海域中的陆地及海洋
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				field[i][j]=sc.next();
				field1[i][j]=field[i][j];
			}
		}
		sc.close();
		
		//1、计算海平面上升之前该海域有多少个岛屿，利用DFS
		int res=0;//res用于存储DFS的次数
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				if(field[i][j].equals("#")) {
				//从有"#"d的地方开始DFS
				dfs(field,i,j);
				res++;
				}
			}
		}
		
		//2、模拟海平面上升
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				if(field1[i][j].equals(".")) {
				fun(field1,i,j);//用于查看陆地上下左右四个方向是否与海洋相邻
				}
			}
		}
		
		//3、计算海平面上升之后还有多少个岛屿，其思路与第一步相同
		int res1=0;
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				if(field1[i][j].equals("#")) {
				dfs(field1,i,j);
				res1++;
				}
			}
		}
		//4、用海平面上升之前海域的岛屿数减去海平面上升之后海域的岛屿数得结果
		System.out.println(res-res1);
		}
}

运行例子：

如上图所示，res为海平面没有上升时海域中岛屿的数量，波浪线以上模拟海平面上升，”*“表示被淹没的岛屿，波浪线以下用于计算海平面上升后海域中存在的岛屿数量，res1为海平面上升之后海域中岛屿的数量。

如果对您有帮助就点个赞吧！嘻嘻嘻！

END

本文地址：https://blog.csdn.net/weixin_43378573/article/details/107687908