今天刚好除夕,先祝大家除夕快乐。作者也希望各位读者在新的一年事业有成,健健康康。
作者最近在准备蓝桥杯java b组,因此在刷相关的题目,希望这里的分享可以帮助到大家。
目录
前言
一、问题分析
1.1问题描述
1.2输入格式:
1.3输出格式
1.4问题分析
二、解体题步骤
2.1录入数据
2.2旋转矩阵部分
2.3矩阵合并部分
2.4求最大土地面积(DFS)
2.5总代码
总结
前言
有关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循环写入
Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int map1[][] = new int[n][n]; int map2[][] = new int[n][n]; for(int i=0;i2.2旋转矩阵部分
public static int[][] xuanzhuan(int map[][]){ int n = map.length; int map_90[][] = new int[n][n]; for(int i=0;i这里的推到难点作者用笔记给大家看,其实难的还是归纳,一行一列归纳很快可以得出结论a[i][j]->a[j][n-i-1]。
2.3矩阵合并部分
public static int[][] hebing(int map1[][],int map2[][],int count) {//count是矩阵1的右上角和左下角的位移差 int n = map1.length; int map[][]; if(count>=n) {//map1在左上角 map = new int[count][2*n]; for(int i=0;i=count-n&&j>=n) { map[i][j]=map2[i+n-count][j-n]; } else { map[i][j] = 0; } } } } else {//map1在左下角 map = new int[2*n-count][2*n]; for(int i=0;i<2*n-count;i++) { for(int j=0;j<2*n;j++) { if(i =n) { map[i][j]=map2[i][j-n]; } else if(i>=n-count&&j
2.4求最大土地面积(DFS)
其实很简单就是找到有1的地方然后慢慢往周围找,如果有1,num就++,防止重复查找,找过的地方就变成0,这样子就可以加快速度,然后四处延申直到找完为止(设计到了迭代)。
public static int max_area(int[][]map) { int max = 0; for(int i=0;i0&&map[i-1][j]==1) { num+=map_dfs(i-1,j,map); } if(i 0&&map[i][j-1]==1) { num+=map_dfs(i,j-1,map); } if(j