題目部分

題目	尋找最大價值的礦堆
難度	難
題目說明	給你一個由 '0'（空地）、'1'（銀礦）、'2'（金礦）組成的的地圖，礦堆只能由上下左右相鄰的金礦或銀礦連接形成。超出地圖范圍可以認為是空地。 假設(shè)銀礦價值 1 ，金礦價值 2 ，請你找出地圖中最大價值的礦堆并輸出該礦堆的價值。
輸入描述	地圖元素信息如： 4 5 22220 00000 00000 01111 ? 4 表示輸入數(shù)據(jù)為 4 行， 5 表示輸入數(shù)據(jù)為 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
說明	無

---

解讀與分析

題目解讀：

如果兩個格子的的關(guān)系為上、下、左、右中的一種情況，且兩個格子的數(shù)據(jù)不為 0，那么認為這兩個格子是相鄰。如果三個格子 A、B、C 中 A 與 B 相鄰，B 與 C 相鄰，那么 A、B、C 放到一個集合中。這樣的集合可能有多個，計算這些集合中所有格子的數(shù)據(jù)之和，并輸出數(shù)據(jù)之和最大的一個。

分析與思路：

分析與思路此題和《華為OD機考算法題：機器人活動區(qū)域》類似。

遍歷所有的格子：
1.?在遍歷過程中，新建一個集合setGrid1，把這個格子放到 setGrid1 中，求出當(dāng)前格子的所有相鄰格子，并依據(jù)相鄰格子求出更多的相鄰格子，直到所有的相鄰格子求出。將得到的相鄰格子放到集合 setGrid1 中，計算集合中所有格子的數(shù)據(jù)之和，設(shè)為 sum1；
2. 繼續(xù)遍歷下個格子，如果下一個格子不在任何一個集合中，則表示這個格子尚未使用過。如果已經(jīng)使用，則繼續(xù)遍歷下一個擱置；如果未使用，新建一個集合setGridn，把它放到 setGridn 中，并繼續(xù)步驟 1 的操作。
3. 最后，比較所有集合的數(shù)據(jù)之和大小，sum1、sum2 …… sumn，輸出最大的值。

---

代碼實現(xiàn)

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;
}

(完)