今天刚好除夕，先祝大家除夕快乐。作者也希望各位读者在新的一年事业有成，健健康康。
作者最近在准备蓝桥杯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;i<n;i++) {
for(int j=0;j<n;j++) {
map1[i][j]=sc.nextInt();
}
}
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {
map2[i][j]=sc.nextInt();
}
}2.2旋转矩阵部分
public static int[][] xuanzhuan(int map[][]){
int n = map.length;
int map_90[][] = new int[n][n];
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {
map_90[j][n-i-1] = map[i][j];//这个归纳可以证明的
}
}
return map_90;
}这里的推到难点作者用笔记给大家看，其实难的还是归纳，一行一列归纳很快可以得出结论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;i++) {
for(int j=0;j<2*n;j++) {
if(i<n&&j<n) {
map[i][j]=map1[i][j];
}
else if(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&&j>=n) {
map[i][j]=map2[i][j-n];
}
else if(i>=n-count&&j<n) {
map[i][j]=map1[i-n+count][j];
}
else {
map[i][j]=0;
}
}
}
}
return map;
}
2.4求最大土地面积（DFS）
其实很简单就是找到有1的地方然后慢慢往周围找，如果有1，num就++，防止重复查找，找过的地方就变成0，这样子就可以加快速度，然后四处延申直到找完为止（设计到了迭代）。
public static int max_area(int[][]map) {
int max = 0;
for(int i=0;i<map.length;i++) {
for(int j=0;j<map[0].length;j++) {
if(map[i][j]==1) {
int num = map_dfs(i,j,map);
if(max<num) {
max=num;
}
}
}
}
return max;
}
private static int map_dfs(int i, int j, int[][] map) {
int num = 0;
if(map[i][j]==0) {
return num;
}
else if(map[i][j]==1) {
map[i][j]=0;
num++;
}
if(i>0&&map[i-1][j]==1) {
num+=map_dfs(i-1,j,map);
}
if(i<map.length-1&&map[i+1][j]==1) {
num+=map_dfs(i+1,j,map);
}
if(j>0&&map[i][j-1]==1) {
num+=map_dfs(i,j-1,map);
}
if(j<map[0].length-1&&map[i][j+1]==1) {
num+=map_dfs(i,j+1,map);
}
return num;
}2.5总代码
package 蓝桥杯备赛;
import java.util.Scanner;
public class 合并区域 {
public static void main(String[] args) {
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;i<n;i++) {
for(int j=0;j<n;j++) {
map1[i][j]=sc.nextInt();
}
}
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {
map2[i][j]=sc.nextInt();
}
}
int map1_90[][] = xuanzhuan(map1);
int map1_180[][] = xuanzhuan(map1_90);
int map1_270[][] = xuanzhuan(map1_180);
int map2_90[][] = xuanzhuan(map2);
int map2_180[][] = xuanzhuan(map2_90);
int map2_270[][] = xuanzhuan(map2_180);
int maps1[][][] = {map1,map1_90,map1_180,map1_270};
int maps2[][][] = {map2,map2_90,map2_180,map2_270};
int count = 2*n-1;
int max = 0;
int maps[][][][]= {maps1,maps2};
while(count>0) {
for(int i=0;i<4;i++) {
for(int j=0;j<4;j++) {
if(max<max_area(hebing(maps[0][i],maps[1][j],count))) {
max = max_area(hebing(maps[0][i],maps[1][j],count));
}
}
}
count--;
}
System.out.print(max);
}
//顺势针转90度
public static int[][] xuanzhuan(int map[][]){
int n = map.length;
int map_90[][] = new int[n][n];
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {
map_90[j][n-i-1] = map[i][j];//这个归纳可以证明的
}
}
return map_90;
}
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;i++) {
for(int j=0;j<2*n;j++) {
if(i<n&&j<n) {
map[i][j]=map1[i][j];
}
else if(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&&j>=n) {
map[i][j]=map2[i][j-n];
}
else if(i>=n-count&&j<n) {
map[i][j]=map1[i-n+count][j];
}
else {
map[i][j]=0;
}
}
}
}
return map;
}
public static int max_area(int[][]map) {
int max = 0;
for(int i=0;i<map.length;i++) {
for(int j=0;j<map[0].length;j++) {
if(map[i][j]==1) {
int num = map_dfs(i,j,map);
if(max<num) {
max=num;
}
}
}
}
return max;
}
private static int map_dfs(int i, int j, int[][] map) {
int num = 0;
if(map[i][j]==0) {
return num;
}
else if(map[i][j]==1) {
map[i][j]=0;
num++;
}
if(i>0&&map[i-1][j]==1) {
num+=map_dfs(i-1,j,map);
}
if(i<map.length-1&&map[i+1][j]==1) {
num+=map_dfs(i+1,j,map);
}
if(j>0&&map[i][j-1]==1) {
num+=map_dfs(i,j-1,map);
}
if(j<map[0].length-1&&map[i][j+1]==1) {
num+=map_dfs(i,j+1,map);
}
return num;
}
}
总结
DFS的实现其实是我今天的一个难度。总的来说实现还是通过递归实现的。
至于作者之前为什么断更了，是因为作者在这年找到了女朋友。也非常感谢女朋友的支持，她几乎每次都会点赞我的文章。文末放一张我和女朋友的照片，嘻嘻！
下学期开始作者会逐渐的更新爬虫js逆向包括验证码啥的，希望大家多多关注哦！！！
版权声明：本文为博主作者：朱笨笨原创文章，版权归属原作者，如果侵权，请联系我们删除！
原文链接：https://blog.csdn.net/weixin_73161549/article/details/136088230
