系列文章目录
前言
本人最近再练习算法，所以会发布一些解题思路，希望大家多指教
一、题目描述
给你一个由’0’(空地)、‘1’(银矿)、‘2’(金矿)组成的地图，矿堆只能由上下左右相邻的金矿或银矿连接形成。超出地图范围可以认为是空地。
假设银矿价值1，金矿价值2，请你找出地图中最大价值的矿堆并输出该矿堆的价值。
二、输入描述
地图元素信息如下：
22220
00000
00000
11111
地图范围最大 300*300
0 <=地图元素 <= 2
三、输出描述
矿堆的最大价值
四、Java代码
//存放每个节点对应上下左右相邻节点的差值
static int[][] arr = new int[][]{{-1,0}, {1,0}, {0,-1}, {0,1}};
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = Integer.parseInt(sc.nextLine());
int[][] arrays = new int[n][];
//获取输入的矿堆信息
for (int i = 0; i < n; i++) {
arrays[i] = Arrays.stream(sc.nextLine().split("")).mapToInt(Integer::parseInt).toArray();
}
//初始化最大能量
int max = 0;
int sum = 0;
for (int i = 0; i < arrays.length; i++) {
for (int j = 0; j < arrays[i].length; j++) {
if(arrays[i][j]>0){
//每次计算能量堆时，将sum值重置为0
sum = 0;
//递归调用该矿点相邻的所有矿堆能量求和
sum = dfs(sum, arrays, i, j);
}
max = Math.max(max, sum);
}
}
System.out.println(max);
}
private static int dfs(int sum, int[][] arrays, int i, int j) {
sum += arrays[i][j];
arrays[i][j] = 0;
for (int k = 0; k < arr.length; k++) {
int x = i + arr[k][0];
int y = j + arr[k][1];
if(x >=0 && x < arrays.length && y >= 0 && y < arrays[i].length && arrays[x][y] > 0){
sum = dfs(sum, arrays, x, y);
}
}
return sum;
}
五、测试用例
输入：
4
22220
22222
02000
11111
输出：
