网站建设公司的商业模式,电子商务网站建设概括,编程开发,个人域名的网站题目部分
题目寻找最大价值的矿堆难度难题目说明给你一个由 0#xff08;空地#xff09;、1#xff08;银矿#xff09;、2#xff08;金矿#xff09;组成的的地图#xff0c;矿堆只能由上下左右相邻的金矿或银矿连接形成。超出地图范围可以认为是空地。 假设银矿价值…题目部分
题目寻找最大价值的矿堆难度难题目说明给你一个由 0空地、1银矿、2金矿组成的的地图矿堆只能由上下左右相邻的金矿或银矿连接形成。超出地图范围可以认为是空地。 假设银矿价值 1 金矿价值 2 请你找出地图中最大价值的矿堆并输出该矿堆的价值。输入描述 地图元素信息如 4 522220 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 ArrayListSetString();SetString usedPoint new HashSetString();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;}SetString newSet new HashSetString();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, SetString usedPoint, SetString 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;
} (完)
