【机试题解法笔记】寻找最大价值的矿堆

题目

给你一个由 '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结果中选取最大的矿堆价值即为最终结果。

算法过程

1. 输入转换：将输入的多行字符串按行分割，再将每行字符串分割为字符数组，并转换为数字数组，形成二维网格。

2. 边界检查：如果网格为空，直接返回 0。

3. 初始化 visited 数组：创建一个与网格大小相同的二维布尔数组，初始值都为false。

4. 双重循环遍历网格：对每个位置(r, c)：

   • 如果该位置已被访问过或为空地（值为 0），跳过。

   • 否则，调用 DFS 函数计算以该位置为起点的矿堆价值。

5. DFS 函数实现：

   • 检查当前位置是否越界、是否已访问或是否为空地，若是则返回 0。

   • 标记当前位置为已访问。

   • 根据当前位置的值（1 为银矿，2 为金矿）确定基础价值。

   • 递归调用 DFS 处理上下左右四个相邻位置，并将结果累加到基础价值上。

6. 更新最大值：每次 DFS 返回后，将结果与当前最大价值比较，更新最大值。

7. 输出结果：遍历结束后，输出记录的最大价值。

复杂度分析

• 时间复杂度：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();
});