「每日LeetCode」2022年2月5日

本文最后更新于：2023年3月19日 晚上

  1. 黄金矿工

1219. 黄金矿工

你要开发一座金矿，地质勘测学家已经探明了这座金矿中的资源分布，并用大小为 m * n 的网格 grid 进行了标注。每个单元格中的整数就表示这一单元格中的黄金数量；如果该单元格是空的，那么就是 0。
为了使收益最大化，矿工需要按以下规则来开采黄金：

  • 每当矿工进入一个单元，就会收集该单元格中的所有黄金。
  • 矿工每次可以从当前位置向上下左右四个方向走。
  • 每个单元格只能被开采（进入）一次。
  • 不得开采（进入）黄金数目为 0 的单元格。
  • 矿工可以从网格中 任意一个 有黄金的单元格出发或者是停止。

​

示例 1：
输入：grid = [[0,6,0],[5,8,7],[0,9,0]] 输出：24 解释： [[0,6,0], [5,8,7], [0,9,0]] 一种收集最多黄金的路线是：9 -> 8 -> 7。
示例 2：
输入：grid = [[1,0,7],[2,0,6],[3,4,5],[0,3,0],[9,0,20]] 输出：28 解释： [[1,0,7], [2,0,6], [3,4,5], [0,3,0], [9,0,20]] 一种收集最多黄金的路线是：1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7。
​

提示：

  • 1 <= grid.length, grid[i].length <= 15
  • 0 <= grid[i][j] <= 100
  • 最多 **25 **个单元格中有黄金。

思路

深度优先回溯算法，计数每一条路径的和即可。每次将遍历过的路径设为 0，防止走重复的路，遍历后回溯设回原来的值。

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
 * @param {number[][]} grid
 * @return {number}
 */
var getMaximumGold = function (grid) {
  let max = 0;
  const visit = (i, j, temp) => {
    if (
      i < 0 ||
      i > grid.length - 1 ||
      j < 0 ||
      j > grid[i].length - 1 ||
      grid[i][j] === 0
    )
      return;
    temp += grid[i][j];
    const tmp = grid[i][j];
    grid[i][j] = 0;

    const top = grid[i - 1] && grid[i - 1][j];
    const bottom = grid[i + 1] && grid[i + 1][j];
    const left = grid[i][j - 1];
    const right = grid[i][j + 1];

    if (top) visit(i - 1, j, temp);
    if (bottom) visit(i + 1, j, temp);
    if (left) visit(i, j - 1, temp);
    if (right) visit(i, j + 1, temp);

    max = Math.max(max, temp);

    grid[i][j] = tmp;
  };
  for (let i = 0; i < grid.length; i++) {
    for (let j = 0; j < grid[i].length; j++) {
      visit(i, j, 0);
    }
  }
  return max;
};