devbox
从前慢现在也慢
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

冲刺蓝桥杯Java b组——合并区域（DFS深度优先）_蓝桥杯合并区域

作者：从前慢现在也慢 | 2024-04-21 03:50:48

赞

踩

蓝桥杯合并区域

今天刚好除夕，先祝大家除夕快乐。作者也希望各位读者在新的一年事业有成，健健康康。

作者最近在准备蓝桥杯java b组，因此在刷相关的题目，希望这里的分享可以帮助到大家。

前言

有关DFS的相关题目及java实现。

一、问题分析

1.1问题描述

        小蓝在玩一款种地游戏。现在他被分配给了两块大小均为N*N的正方形区域。这两块区域都按照N*N的规格进行了均等划分，划分成了若干块面积相同的小区域，其中每块小区域要么是岩石，要么就是土壤，在垂直或者水平方向上相邻的土壤可以组成一块土地。现在小蓝想要对这两块区域沿着边缘进行合并，他想知道合并以后可以得到的最大的一块土地的面积是多少（土地的面积就是土地中土壤小区域的块数）

1.2输入格式：

        第一行一个整数。

        接下来N行表示第一块区域，每行N个值为0或1的的整数，相邻的整数之间用空格进行分隔。值为0或1的整数，相邻的整数之间用空格进行分隔。值为0表示这块区域为演示，值为1表示这块区域为土壤。

1.3输出格式

        一个整数表示将两块区域合并后可以产生的最大土地的面积。

1.4问题分析

        这是一个典型的DFS或者BFS问题，就是将两个n*n的矩阵以任意的形式拼接。其实就是求所有连接的1的最大数量。只要便利所有的拼接情况写一个递归就好了。

        然后将程序分成4部分：

第一部分：录入数据

第二部分：将矩阵旋转（一个xuanzhuan函数）

第三部分：将举证拼接（2个矩阵拼接然后补成一个大矩形，空的地方填写0）

第四部分：求最大土地面积（DFS）

二、解体题步骤

2.1录入数据

        简单的两个新建二维数组，然后两个for循环写入

  1. Scanner sc = new Scanner(System.in);
  2. int n = sc.nextInt();
  3. int map1[][]  = new int[n][n];
  4. int map2[][]  = new int[n][n];
  5. 		
  6. for(int i=0;i<n;i++) {
  7. 	for(int j=0;j<n;j++) {
  8. 		map1[i][j]=sc.nextInt();
  9. 		}
  10. 	}
  11. for(int i=0;i<n;i++) {
  12. 	for(int j=0;j<n;j++) {
  13. 		map2[i][j]=sc.nextInt();
  14. 		}
  15. 	}

2.2旋转矩阵部分

  1. public static int[][] xuanzhuan(int map[][]){
  2. 		int n = map.length;
  3. 		int map_90[][] = new int[n][n];
  4. 		for(int i=0;i<n;i++) {
  5. 			for(int j=0;j<n;j++) {
  6. 				map_90[j][n-i-1] = map[i][j];//这个归纳可以证明的
  7. 			}
  8. 		}
  9. 		return map_90;
  10. 	}

        这里的推到难点作者用笔记给大家看，其实难的还是归纳，一行一列归纳很快可以得出结论a[i][j]->a[j][n-i-1]。 

2.3矩阵合并部分 

    

  1. public static int[][] hebing(int map1[][],int map2[][],int count) {//count是矩阵1的右上角和左下角的位移差
  2. 		int n = map1.length;
  3. 		int map[][];
  4. 		if(count>=n) {//map1在左上角
  5. 			map = new int[count][2*n];
  6. 			for(int i=0;i<count;i++) {
  7. 				for(int j=0;j<2*n;j++) {
  8. 					if(i<n&&j<n) {
  9. 						map[i][j]=map1[i][j];
  10. 					}
  11. 					else if(i>=count-n&&j>=n) {
  12. 						map[i][j]=map2[i+n-count][j-n];
  13. 					}
  14. 					else {
  15. 						map[i][j] = 0;
  16. 					}
  17. 				}
  18. 			}
  19. 		}
  20. 		else {//map1在左下角
  21. 			map = new int[2*n-count][2*n];
  22. 			for(int i=0;i<2*n-count;i++) {
  23. 				for(int j=0;j<2*n;j++) {
  24. 					if(i<n&&j>=n) {
  25. 						map[i][j]=map2[i][j-n];
  26. 					}
  27. 					else if(i>=n-count&&j<n) {
  28. 						map[i][j]=map1[i-n+count][j];
  29. 					}
  30. 					else {
  31. 						map[i][j]=0;
  32. 					}
  33. 				}
  34. 			}
  35. 		}
  36. 		
  37. 		return map;
  38. 	}

    

2.4求最大土地面积（DFS）

        其实很简单就是找到有1的地方然后慢慢往周围找，如果有1，num就++，防止重复查找，找过的地方就变成0，这样子就可以加快速度，然后四处延申直到找完为止（设计到了迭代）。

  1. public static int max_area(int[][]map) {
  2. 		int max = 0;
  3. 		for(int i=0;i<map.length;i++) {
  4. 			for(int j=0;j<map[0].length;j++) {
  5. 				if(map[i][j]==1) {
  6. 					int num = map_dfs(i,j,map);
  7. 					if(max<num) {
  8. 						max=num;
  9. 					}
  10. 				}
  11. 			}
  12. 		}
  13. 		return max;
  14. 	}
  15.  
  16. 	private static int map_dfs(int i, int j, int[][] map) {
  17. 		int num = 0;
  18. 		if(map[i][j]==0) {
  19. 			return num;
  20. 		}
  21. 		else if(map[i][j]==1) {
  22. 			map[i][j]=0;
  23. 			num++;
  24. 		}
  25. 		if(i>0&&map[i-1][j]==1) {
  26. 			num+=map_dfs(i-1,j,map);
  27. 		}
  28. 		if(i<map.length-1&&map[i+1][j]==1) {
  29. 			num+=map_dfs(i+1,j,map);
  30. 		}
  31. 		if(j>0&&map[i][j-1]==1) {
  32. 			num+=map_dfs(i,j-1,map);
  33. 		}
  34. 		if(j<map[0].length-1&&map[i][j+1]==1) {
  35. 			num+=map_dfs(i,j+1,map);
  36. 		}
  37. 		return num;
  38. 	}

 2.5总代码

  1. package 蓝桥杯备赛;
  2.  
  3. import java.util.Scanner;
  4.  
  5. public class 合并区域 {
  6.  
  7. 	public static void main(String[] args) {
  8. 		Scanner sc = new Scanner(System.in);
  9. 		int n = sc.nextInt();
  10. 		int map1[][]  = new int[n][n];
  11. 		int map2[][]  = new int[n][n];
  12. 		
  13. 		for(int i=0;i<n;i++) {
  14. 			for(int j=0;j<n;j++) {
  15. 				map1[i][j]=sc.nextInt();
  16. 			}
  17. 		}
  18. 		
  19. 		for(int i=0;i<n;i++) {
  20. 			for(int j=0;j<n;j++) {
  21. 				map2[i][j]=sc.nextInt();
  22. 			}
  23. 		}
  24. 		int map1_90[][] = xuanzhuan(map1);
  25. 		int map1_180[][] = xuanzhuan(map1_90);
  26. 		int map1_270[][] = xuanzhuan(map1_180);
  27. 		
  28. 		int map2_90[][] = xuanzhuan(map2);
  29. 		int map2_180[][] = xuanzhuan(map2_90);
  30. 		int map2_270[][] = xuanzhuan(map2_180);
  31. 		
  32. 		int maps1[][][] = {map1,map1_90,map1_180,map1_270};
  33. 		int maps2[][][] = {map2,map2_90,map2_180,map2_270};
  34. 		
  35. 		int count = 2*n-1;
  36. 		int max = 0;
  37. 		
  38. 		int maps[][][][]= {maps1,maps2};
  39. 		
  40. 		while(count>0) {
  41. 			for(int i=0;i<4;i++) {
  42. 				for(int j=0;j<4;j++) {
  43. 					if(max<max_area(hebing(maps[0][i],maps[1][j],count))) {
  44. 						max = max_area(hebing(maps[0][i],maps[1][j],count));
  45. 					}
  46. 				}
  47. 			}
  48. 			count--;
  49. 		}
  50. 		System.out.print(max);
  51. 	}
  52. 	
  53. 	//顺势针转90度
  54. 	public static int[][] xuanzhuan(int map[][]){
  55. 		int n = map.length;
  56. 		int map_90[][] = new int[n][n];
  57. 		for(int i=0;i<n;i++) {
  58. 			for(int j=0;j<n;j++) {
  59. 				map_90[j][n-i-1] = map[i][j];//这个归纳可以证明的
  60. 			}
  61. 		}
  62. 		return map_90;
  63. 	}
  64. 	
  65. 	public static int[][] hebing(int map1[][],int map2[][],int count) {//count是矩阵1的右上角和左下角的位移差
  66. 		int n = map1.length;
  67. 		int map[][];
  68. 		if(count>=n) {//map1在左上角
  69. 			map = new int[count][2*n];
  70. 			for(int i=0;i<count;i++) {
  71. 				for(int j=0;j<2*n;j++) {
  72. 					if(i<n&&j<n) {
  73. 						map[i][j]=map1[i][j];
  74. 					}
  75. 					else if(i>=count-n&&j>=n) {
  76. 						map[i][j]=map2[i+n-count][j-n];
  77. 					}
  78. 					else {
  79. 						map[i][j] = 0;
  80. 					}
  81. 				}
  82. 			}
  83. 		}
  84. 		else {//map1在左下角
  85. 			map = new int[2*n-count][2*n];
  86. 			for(int i=0;i<2*n-count;i++) {
  87. 				for(int j=0;j<2*n;j++) {
  88. 					if(i<n&&j>=n) {
  89. 						map[i][j]=map2[i][j-n];
  90. 					}
  91. 					else if(i>=n-count&&j<n) {
  92. 						map[i][j]=map1[i-n+count][j];
  93. 					}
  94. 					else {
  95. 						map[i][j]=0;
  96. 					}
  97. 				}
  98. 			}
  99. 		}
  100. 		
  101. 		return map;
  102. 	}
  103. 	
  104. 	
  105. 	public static int max_area(int[][]map) {
  106. 		int max = 0;
  107. 		for(int i=0;i<map.length;i++) {
  108. 			for(int j=0;j<map[0].length;j++) {
  109. 				if(map[i][j]==1) {
  110. 					int num = map_dfs(i,j,map);
  111. 					if(max<num) {
  112. 						max=num;
  113. 					}
  114. 				}
  115. 			}
  116. 		}
  117. 		return max;
  118. 	}
  119.  
  120. 	private static int map_dfs(int i, int j, int[][] map) {
  121. 		int num = 0;
  122. 		if(map[i][j]==0) {
  123. 			return num;
  124. 		}
  125. 		else if(map[i][j]==1) {
  126. 			map[i][j]=0;
  127. 			num++;
  128. 		}
  129. 		if(i>0&&map[i-1][j]==1) {
  130. 			num+=map_dfs(i-1,j,map);
  131. 		}
  132. 		if(i<map.length-1&&map[i+1][j]==1) {
  133. 			num+=map_dfs(i+1,j,map);
  134. 		}
  135. 		if(j>0&&map[i][j-1]==1) {
  136. 			num+=map_dfs(i,j-1,map);
  137. 		}
  138. 		if(j<map[0].length-1&&map[i][j+1]==1) {
  139. 			num+=map_dfs(i,j+1,map);
  140. 		}
  141. 		return num;
  142. 	}
  143. }

总结

        DFS的实现其实是我今天的一个难度。总的来说实现还是通过递归实现的。

        至于作者之前为什么断更了，是因为作者在这年找到了女朋友。也非常感谢女朋友的支持，她几乎每次都会点赞我的文章。文末放一张我和女朋友的照片，嘻嘻！

下学期开始作者会逐渐的更新爬虫js逆向包括验证码啥的，希望大家多多关注哦！！！

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/460881
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号