华为OD机试真题【寻找最大价值的矿堆】

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;i<grid.length;i++){for(int j = 0; j<grid[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(i<0||j<0 || i>=grid.length || j>= grid[0].length|| grid[i][j]==0) return 0;//定义一个变量表示岛屿的面积，就是包含几个陆地int sum = 1;//将陆地改为海洋，防止重复陆地重复遍历。grid[i][j] =0;//遍历上方元素，每遍历一次陆地就加一sum += dfs(grid,i+1,j);//遍历下方元素sum +=dfs(grid,i-1,j);//遍历右边元素sum +=dfs(grid,i,j+1);//遍历左边元素sum += dfs(grid,i,j-1);return sum;}