网站源码推荐,网站代码关键词标题,商标设计网排行,经销做网站都有什么好处题目 给你一个由0(空地)、1(银矿)、2(金矿)组成的的地图#xff0c;矿堆只能由上下左右相邻的金矿或银矿连接形成。超出地图范围可以认为是空地。 假设银矿价值1#xff0c;金矿价值2#xff0c;请你找出地图中最大价值的矿堆并输出该矿堆的价值 输入描述 地图元素信息如: 2…题目 给你一个由0(空地)、1(银矿)、2(金矿)组成的的地图矿堆只能由上下左右相邻的金矿或银矿连接形成。超出地图范围可以认为是空地。 假设银矿价值1金矿价值2请你找出地图中最大价值的矿堆并输出该矿堆的价值 输入描述 地图元素信息如: 22220 00000 00000 11111 地图范围最大300*300 0地图元素2 输出描述: 矿堆的最大价值 示例1 输入: 22220 00000 00000 01111 输出: 8 示例2 输入: 22220 00020 00010 01111 输出: 15 示例3 输入: 20000 00120 00000 00111 输出: 3 思路 遍历矿堆如果当前值不等于0等于1或等于2那么从当前值计算所有相邻的总价值是多少 将本轮遍历产生的总价值和上次的总价值比较得到较大值 遍历完成后就能得到矿堆的最大价值 问题的关键在于怎么求所有相邻的总价值根据题目描述总价值等于当前值上总价值下总价值左总价值右总价值。 设计 dfs(grid,i,j)函数grid是一个二维数组表示矿堆ij代表开始计算位置。 定义递归终止条件如果i,j超出数组范围或者grid[i][j]0,那么 直接返回0 定义结果res的初始值resgrid[i][j] 递归计算与当前位置的相邻上下左右四个位置位置的累加价值用res加上相邻的值 最后返回res即可 题解
package hwod;import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;public class FindKMaxVal {public static void main(String[] args) {Scanner sc new Scanner(System.in);ListString list new ArrayList();while (sc.hasNextLine()) {String line sc.nextLine();if (.equals(line)) break;list.add(line);}int n list.size();int[][] pile new int[n][list.get(0).length()];//字符数组转整形数组for (int i 0; i n; i) {String line list.get(i);for (int j 0; j line.length(); j) {pile[i][j] line.charAt(j) - 0;}}System.out.println(findMaxVal(pile));}private static int findMaxVal(int[][] pile) {int m pile.length;int res 0;for (int i 0; i m; i) {for (int j 0; j pile[i].length; j) {if (pile[i][j] 1 || pile[i][j] 2) {int cur dfs(i, j, pile);res Math.max(res, cur);}}}return res;}private static int dfs(int i, int j, int[][] pile) {int m pile.length, n pile[0].length;if (i m || j n || i 0 || j 0 || (pile[i][j] ! 1 pile[i][j] ! 2)) return 0;int res pile[i][j];pile[i][j] 0;res dfs(i 1, j, pile) dfs(i, j 1, pile) dfs(i - 1, j, pile) dfs(i, j - 1, pile);return res;}
}
推荐
如果你对本系列的其他题目感兴趣可以参考华为OD机试真题及题解JAVA查看当前专栏更新的所有题目。
