华为OD机考算法题：寻找最大价值的矿堆

题目部分

题目	寻找最大价值的矿堆
难度	难
题目说明	给你一个由 '0'（空地）、'1'（银矿）、'2'（金矿）组成的的地图，矿堆只能由上下左右相邻的金矿或银矿连接形成。超出地图范围可以认为是空地。 假设银矿价值 1 ，金矿价值 2 ，请你找出地图中最大价值的矿堆并输出该矿堆的价值。
输入描述	地图元素信息如： 4 5 22220 00000 00000 01111   4 表示输入数据为 4 行， 5 表示输入数据为 5 列； 地图范围最大为 300 * 300； 0 <= 地图元素 <= 2。
输出描述	矿堆的最大价值。
补充说明	无
------------------------------------------------------
示例
示例1
输入	4 5 22220 00000 00000 01111
输出	8
说明	无
示例2
输入	4 5 22220 00020 00010 01111
输出	15
说明	无
示例2
输入	4 5 20000 00020 00000 00111
输出	3
说明	无

---

解读与分析

题目解读：

如果两个格子的的关系为上、下、左、右中的一种情况，且两个格子的数据不为 0，那么认为这两个格子是相邻。如果三个格子 A、B、C 中 A 与 B 相邻，B 与 C 相邻，那么 A、B、C 放到一个集合中。这样的集合可能有多个，计算这些集合中所有格子的数据之和，并输出数据之和最大的一个。

分析与思路：

分析与思路此题和《华为OD机考算法题：机器人活动区域》类似。

遍历所有的格子：
1. 在遍历过程中，新建一个集合setGrid1，把这个格子放到 setGrid1 中，求出当前格子的所有相邻格子，并依据相邻格子求出更多的相邻格子，直到所有的相邻格子求出。将得到的相邻格子放到集合 setGrid1 中，计算集合中所有格子的数据之和，设为 sum1；
2. 继续遍历下个格子，如果下一个格子不在任何一个集合中，则表示这个格子尚未使用过。如果已经使用，则继续遍历下一个搁置；如果未使用，新建一个集合setGridn，把它放到 setGridn 中，并继续步骤 1 的操作。
3. 最后，比较所有集合的数据之和大小，sum1、sum2 …… sumn，输出最大的值。

---

代码实现

Java代码

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.Set;
import java.util.HashSet;/*** 寻找最大价值的矿堆* * @since 2023.10.25* @version 0.1* @author Frank**/
public class MaxMineValue {public static void main(String[] args) {Scanner sc = new Scanner(System.in);while (sc.hasNext()) {String input = sc.nextLine();String[] inputStr = input.split(" ");int row = Integer.parseInt(inputStr[0]);int column = Integer.parseInt(inputStr[1]);int[][] mineMap = new int[row][column];for (int i = 0; i < row; i++) {input = sc.nextLine();// inputStr.length == columnint[] eachColumn = new int[column];for (int j = 0; j < input.length(); j++) {eachColumn[j] = Integer.parseInt(input.substring(j, j + 1));}mineMap[i] = eachColumn;}processMaxMineValue(mineMap);}}private static void processMaxMineValue(int[][] mineMap) {List minSetList = new ArrayList<Set<String>>();Set<String> usedPoint = new HashSet<String>();int maxSum = 0;for (int i = 0; i < mineMap.length; i++) {for (int j = 0; j < mineMap[0].length; j++) {String pos = i + " " + j;if (usedPoint.contains(pos)) {continue;}Set<String> newSet = new HashSet<String>();usedPoint.add(pos);newSet.add(pos);int sum = mineMap[i][j];sum += getAdjacentGridsSum(i, j, usedPoint, newSet, mineMap);if (sum > maxSum) {maxSum = sum;}minSetList.add(newSet);}}System.out.println(maxSum);}private static int getAdjacentGridsSum(int i, int j, Set<String> usedPoint, Set<String> newSet, int[][] mineMap) {int[][] possiblePoint = { { i, j - 1 }, { i, j + 1 }, { i + 1, j }, { i - 1, j } };int sum = 0;for (int k = 0; k < possiblePoint.length; k++) {int[] currentPoint = possiblePoint[k];if (currentPoint[0] < 0 || currentPoint[1] < 0 || currentPoint[0] >= mineMap.length|| currentPoint[1] >= mineMap[0].length) {continue;}String pos = currentPoint[0] + " " + currentPoint[1];if (usedPoint.contains(pos)) {continue;}if (mineMap[currentPoint[0]][currentPoint[1]] == 0) {continue;}usedPoint.add(pos);newSet.add(pos);sum += mineMap[currentPoint[0]][currentPoint[1]];sum += getAdjacentGridsSum(currentPoint[0], currentPoint[1], usedPoint, newSet, mineMap);}return sum;}}

在以上算法中，使用了 minSetList 记录每个矿堆的坐标集合，在实际计算时，不要求输出矿堆坐标，所以 minSetList 是可以省掉的。

JavaScript代码

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;
void async function() {while (line = await readline()) {var inputArr = line.split(" ");var row = parseInt(inputArr[0]);var column = parseInt(inputArr[1]);var mineMap = new Array();for (var i = 0; i < row; i++) {line = await readline();var eachContent = new Array();for (var j = 0; j < column; j++) {eachContent[j] = line.substring(j, j + 1);}mineMap[i] = eachContent;}processMaxMineValue(mineMap);}
}();function processMaxMineValue(mineMap) {var minSetList = new Array();var usedPoint = new Set();var maxSum = 0;for (var i = 0; i < mineMap.length; i++) {for (var j = 0; j < mineMap[0].length; j++) {var pos = i + " " + j;if (usedPoint.has(pos)) {continue;}var newSet = new Set();usedPoint.add(pos);newSet.add(pos);var sum = parseInt( mineMap[i][j] );sum += getAdjacentGridsSum(i, j, usedPoint, newSet, mineMap);if (sum > maxSum) {maxSum = sum;}minSetList.push(newSet);}}console.log( maxSum );
}function getAdjacentGridsSum(i, j, usedPoint, newSet, mineMap) {var possiblePoint = [[i, j - 1],[i, j + 1],[i + 1, j],[i - 1, j]];var sum = 0;for (var k = 0; k < possiblePoint.length; k++) {var currentPoint = possiblePoint[k];if (currentPoint[0] < 0 || currentPoint[1] < 0 || currentPoint[0] >= mineMap.length ||currentPoint[1] >= mineMap[0].length) {continue;}var pos = currentPoint[0] + " " + currentPoint[1];if (usedPoint.has(pos)) {continue;}var curValue = parseInt( mineMap[currentPoint[0]][currentPoint[1]] );if ( curValue == 0) {continue;}usedPoint.add(pos);newSet.add(pos);sum += curValue;sum += getAdjacentGridsSum(currentPoint[0], currentPoint[1], usedPoint, newSet, mineMap);}return sum;
}

(完)