淄博网站制作定制,个人网站的留言板数据库怎么做,电脑维修网站模板下载,哈尔滨市建设工程招投标1、题目描述
【寻找最大价值的矿堆】 给你一个由 ‘0’#xff08;空地#xff09;、’1’#xff08;银矿#xff09;、’2’#xff08;金矿#xff09;组成的的地图#xff0c; 矿堆只能由上下左右相邻的金矿或银矿连接形成。超出地图范围可以认为是空地。 假设银矿…1、题目描述
【寻找最大价值的矿堆】 给你一个由 ‘0’空地、’1’银矿、’2’金矿组成的的地图 矿堆只能由上下左右相邻的金矿或银矿连接形成。超出地图范围可以认为是空地。 假设银矿价值1 金矿价值2请你找出地图中最大价值的矿堆并输出该矿堆的价值。 **【输入描述】**地图元素信息如下 22220 00000 00000 11111 地图范围最大 300*300 0 地图元素 2 【输出描述】 矿堆的最大价值 8 【输入】 22220 00000 00000 01111 【输出】 8 【输入】 22220 00020 00010 01111 【输出】 15
2、解题思路
此题与【岛屿的最大面试】题类似可用dfs回溯遍历的方法感染矩阵的位置即将符合题意的方向的1都变成0统计需要多少次才能将矩阵中所有的值都变成0。
3、参考代码
import java.util.Arrays;
import java.util.Scanner;/*** Author* Date 2023/6/11 10:15*/
public class 寻找最大价值的矿堆 {public static void main(String[] args) {Scanner in new Scanner(System.in);while (in.hasNext()) {int n Integer.parseInt(in.nextLine());int[][] array new int[n][];for (int col 0; col n; col) {array[col] Arrays.stream(in.nextLine().split()).mapToInt(Integer::parseInt).toArray();}int maxValue 0;// int maxSum 0;for (int i 0; i n; i) {for (int j 0; j array[i].length; j) {if (array[i][j] ! 0) {maxValue Math.max(maxValue, dfs(array, i, j));// maxSum Math.max(maxSum, dfs(array, i, j, 0));}}}System.out.println(maxValue);//System.out.println(maxSum);}}// 方法一public static int dfs(int[][] array, int i, int j) {if (i 0 || j 0 || i array.length || j array[i].length || array[i][j] 0) {return 0;}int sum array[i][j];array[i][j] 0;sum dfs(array, i 1, j);sum dfs(array, i - 1, j);sum dfs(array, i, j 1);sum dfs(array, i, j - 1);return sum;}// 方法二public static int[][] distances {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};public static int dfs(int[][] array, int i, int j, int maxSum) {if (i 0 || j 0 || i array.length || j array[i].length || array[i][j] 0) {return maxSum;}maxSum array[i][j];array[i][j] 0;for (int[] dis : distances) {int newI i dis[0];int newJ j dis[1];if (newI 0 || newJ 0 || newI array.length || newJ array[newI].length || array[newI][newJ] 0) {continue;}maxSum dfs(array, newI, newJ, maxSum);}return maxSum;}}4、相似题目
1岛屿的面积 //可以看图理解在加上记住这个模板。public int maxAreaOfIsland(int[][] grid) {//定义一个表示岛屿的面积int max 0;//这两个for循环是来遍历整张二维格上的所有陆地的。//i 表示行j表示列for(int i 0;igrid.length;i){for(int j 0; jgrid[0].length;j){//陆地的格if(grid[i][j]1){//取出最大的面积max Math.max(max,dfs(grid,i,j));} }}//返回最大的陆地面积return max;}public int dfs(int[][] grid,int i,int j){//当超出岛屿边界上下左右的时候就直接退出特别要加上当遍历到海洋的时候也要退出if(i0||j0 || igrid.length || j grid[0].length|| grid[i][j]0) return 0;//定义一个变量表示岛屿的面积就是包含几个陆地int sum 1;//将陆地改为海洋防止重复陆地重复遍历。grid[i][j] 0;//遍历上方元素每遍历一次陆地就加一sum dfs(grid,i1,j);//遍历下方元素sum dfs(grid,i-1,j);//遍历右边元素sum dfs(grid,i,j1);//遍历左边元素sum dfs(grid,i,j-1);return sum;}
