LeetCode 1219. 黄金矿工

约 6 分钟
文章信息 7 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 腾讯 快手
标签
数组 矩阵 回溯

题目描述

✅ 1219. 黄金矿工

image-20260928230422416

image-20260928230422417

题意分析

可以从任意有黄金的格子出发，每次向上下左右移动，不能进入零格，也不能在同一路径中重复进入格子；允许随时停止，求一条路径能收集的最大黄金量。

不能只求整个连通区域的黄金总和，因为一条不重复经过格子的路径未必能覆盖整个区域。题目最多只有 25 个黄金格，可以枚举起点并回溯搜索所有合法路径。

解法：原地标记回溯

核心思路

[!blue]

dfs(row, col) 返回在当前已走路径限制下，从这个格子出发还能收集的最大黄金量，包含当前格子的黄金。先保存当前值 gold，再把格子临时置零，让后续搜索把它当成不可进入的位置。

接下来尝试四个方向中未越界且仍有黄金的邻居。一条路径在当前格子之后只能选择一个方向，因此取各次递归结果的最大值 bestNext，不能把分支相加。令 bestNext 初始为零，表示可以停在当前格子；没有合法邻居时也会自然结束。

返回前恢复当前格子的原值，再返回 gold + bestNext。子调用也会恢复自己访问的格子，所以尝试下一个方向时，只有当前递归路径仍被标记，兄弟分支与后续起点不会互相影响。

同一坐标在不同路径下可能有不同的可走邻居，结果还依赖已经占用的格子集合，不能只按坐标缓存答案。枚举所有非零起点并取最大值，才能覆盖起点未知的情况。

解题步骤

  1. 初始化答案为零，遍历网格中的每个非零格子，把它作为起点调用 DFS。
  2. 进入格子后保存黄金量并置零，阻止当前路径再次进入。
  3. 搜索四邻中的合法下一步，用递归返回值更新 bestNext。
  4. 恢复当前格子，返回当前黄金加最佳后续；外层用各起点结果更新答案。

全零网格没有可选起点，答案保持为零；每次 DFS 都恢复网格，函数返回时输入也保持原样。

代码实现

class Solution {
    private static final int[][] DIRECTIONS = {
        {1, 0},
        {-1, 0},
        {0, 1},
        {0, -1}
    };

    public int getMaximumGold(int[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;
        int ans = 0;

        for (int row = 0; row < rows; row++) {
            for (int col = 0; col < cols; col++) {
                if (grid[row][col] > 0) {
                    ans = Math.max(ans, dfs(grid, row, col));
                }
            }
        }

        return ans;
    }

    private int dfs(int[][] grid, int row, int col) {
        int gold = grid[row][col];

        // 临时占用当前格，本条路径不能再次进入。
        grid[row][col] = 0;

        // 一条路径只能选择一个后续方向，取最大贡献而不是把分支相加。
        int bestNext = 0;

        for (int[] direction : DIRECTIONS) {
            int nextRow = row + direction[0];
            int nextCol = col + direction[1];

            if (isValid(grid, nextRow, nextCol)) {
                bestNext = Math.max(bestNext, dfs(grid, nextRow, nextCol));
            }
        }

        // 恢复原值，兄弟分支与其他起点仍能正常使用。
        grid[row][col] = gold;

        return gold + bestNext;
    }

    private boolean isValid(int[][] grid, int row, int col) {
        return row >= 0
                && row < grid.length
                && col >= 0
                && col < grid[0].length
                && grid[row][col] > 0;
    }
}

func getMaximumGold(grid [][]int) int {
    rows := len(grid)
    cols := len(grid[0])
    directions := [][2]int{
        {1, 0},
        {-1, 0},
        {0, 1},
        {0, -1},
    }

    var dfs func(row int, col int) int
    dfs = func(row int, col int) int {
        gold := grid[row][col]
        // 临时占用当前格，本条路径不能再次进入。
        grid[row][col] = 0

        // 一条路径只能选择一个后续方向，取最大贡献而不是把分支相加。
        bestNext := 0
        for _, direction := range directions {
            nextRow := row + direction[0]
            nextCol := col + direction[1]
            if nextRow >= 0 && nextRow < rows &&
                nextCol >= 0 && nextCol < cols &&
                grid[nextRow][nextCol] > 0 {
                nextGold := dfs(nextRow, nextCol)
                if nextGold > bestNext {
                    bestNext = nextGold
                }
            }
        }

        // 恢复原值，兄弟分支与其他起点仍能正常使用。
        grid[row][col] = gold
        return gold + bestNext
    }

    ans := 0
    for row := 0; row < rows; row++ {
        for col := 0; col < cols; col++ {
            if grid[row][col] > 0 {
                gold := dfs(row, col)
                if gold > ans {
                    ans = gold
                }
            }
        }
    }

    return ans
}

复杂度分析

  • 时间复杂度：上界为 $O(mn+g3^g)$，其中 g 是黄金格数。扫描网格需要 $O(mn)$；每个起点第一步至多四个方向，之后不能立即走回上一格，至多三个方向，路径长度不超过 g，再乘上至多 g 个起点。
  • 空间复杂度：$O(g+1)$，当前路径递归栈。

关键点总结

[!green]

  • 访问标记只属于当前路径，分支结束必须撤销。
  • 零格既代表原本不可走，也用于临时占用。

易错点总结

[!yellow]

  • 把访问标记永久保留，会影响后续起点与分支。
  • 只从最大值格子出发，可能漏掉其他连通区域的更优路径。
  • 允许穿过零格，会连接本来无法相通的黄金。

相似题目

题目 难度 关联与区别
79. 单词搜索 中等 同样回溯当前路径并在返回时恢复访问标记，本题最大化金币和，原题匹配指定单词。
980. 不同路径 III 困难 原题必须访问全部可走格一次，本题可从任意金矿开始并选择较优的部分路径。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2023/65416088
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！