【机试题解法笔记】寻找最大价值的矿堆
题目
给你一个由 '0'(空地)、'1'(银矿)、'2'(金矿) 组成的的地图，矿堆只能由上下左右相邻的金矿或银矿连接形成。超出地图范围可以认为是空地。
假设银矿价值 1，金矿价值 2，请你找出地图中最大价值的矿堆并输出该矿堆的价值。
输入描述
地图元素信息如：
22220
00000
00000
11111
地图范围最大 300*300
0 ≤ 地图元素 ≤ 2
输出描述
矿堆的最大价值
用例
| 输入 | 输出 |
|---|---|
| 22220 00000 00000 01111 | 8 |
| 22220 00020 00010 01111 | 15 |
| 20000 00020 00000 00111 | 3 |
思考
以矩阵中的每个不为0的位置作为起点深度优先搜索矿堆，遇到0就回退，用visited数组记录访问过的矿堆，统计路径上的矿产价值总和。在多轮的不同的起点DFS结果中选取最大的矿堆价值即为最终结果。
算法过程
-
输入转换：将输入的多行字符串按行分割，再将每行字符串分割为字符数组，并转换为数字数组，形成二维网格。
-
边界检查：如果网格为空，直接返回 0。
-
初始化 visited 数组：创建一个与网格大小相同的二维布尔数组，初始值都为
false。 -
双重循环遍历网格：对每个位置
(r, c)：-
如果该位置已被访问过或为空地（值为 0），跳过。
-
否则，调用 DFS 函数计算以该位置为起点的矿堆价值。
-
-
DFS 函数实现：
-
检查当前位置是否越界、是否已访问或是否为空地，若是则返回 0。
-
标记当前位置为已访问。
-
根据当前位置的值（1 为银矿，2 为金矿）确定基础价值。
-
递归调用 DFS 处理上下左右四个相邻位置，并将结果累加到基础价值上。
-
-
更新最大值：每次 DFS 返回后，将结果与当前最大价值比较，更新最大值。
-
输出结果：遍历结束后，输出记录的最大价值。
复杂度分析
-
时间复杂度：O (m×n)，其中 m 和 n 分别是地图的行数和列数。每个位置最多被访问一次。
-
空间复杂度：O (m×n)，主要用于存储 visited 数组和递归调用栈的空间。
参考代码
function solution() {const n = parseInt(readline());const grid = [];for (let i = 0; i < n; i++) {grid[i] = readline().split("").map(Number);}const rows = grid.length;if (rows === 0) {console.log(0);return;}const cols = grid[0].length;const visited = Array.from({ length: rows }, () => Array(cols).fill(false));let maxValue = 0;function dfs(r, c) {if (r < 0 ||r >= rows ||c < 0 ||c >= cols ||visited[r][c] ||grid[r][c] === 0) {return 0;}visited[r][c] = true;return grid[r][c] + dfs(r + 1, c) + dfs(r - 1, c) + dfs(r, c + 1) + dfs(r, c - 1);}for (let r = 0; r < rows; r++) {for (let c = 0; c < cols; c++) {if (!visited[r][c] && grid[r][c] !== 0) {const currentValue = dfs(r, c);maxValue = Math.max(maxValue, currentValue);}}}console.log(maxValue);
}const cases = [`4
22220
00000
00000
01111`,
`4
22220
00020
00010
01111`,
`4
20000
00020
00000
00111`
];
let caseIndex = 0;
let lineIndex = 0;const readline = (function () {let lines = [];return function () {if (lineIndex === 0) {lines = cases[caseIndex].trim().split("\n").map((line) => line.trim());}return lines[lineIndex++];};
})();cases.forEach((_, i) => {caseIndex = i;lineIndex = 0;solution();
});