---

1219. 黄金矿工

• 标签：数组、回溯、矩阵
• 难度：中等

题目链接

• 1219. 黄金矿工 - 力扣

题目大意

描述：给定一个 $m \times n$ 的网格 $grid$，每个格子里是黄金数量（$0$ 表示没有黄金）。矿工从任意有黄金的格子开始，每次可以向上下左右四个方向移动一格。矿工不能重复进入同一个格子，也不能进入黄金数量为 $0$ 的格子。

要求：返回矿工能收集到的最大黄金数。

说明：

• $1 \le m, n \le 15$。
• $0 \le grid[i][j] \le 100$。
• 最多有 $25$ 个非零格子。

题目链接

• 1219. 黄金矿工 - 力扣

解题思路

思路 1：回溯（DFS）

1. 核心思想

最多 $25$ 个非零格子，搜索空间有限。可以从每个有黄金的格子出发，DFS 探索所有可能的路径，取路径上黄金总和的最大值。

2. 选择、限制与终止

• 选择：从当前格子向上下左右四个方向移动。
• 限制：不能走出网格，不能进入 $0$ 格子，不能重复访问（用 $visited$ 标记）。
• 终止：当四个方向都不能走时（即走到死胡同），更新最大黄金数。

3. 具体步骤

第 1 步：遍历网格，从每个有黄金的格子开始 DFS。

第 2 步：定义 DFS 函数 $dfs(i, j, current\_gold)$：

• 收集当前格子的黄金：$current\_gold += grid[i][j]$。
• 标记 $(i, j)$ 已访问。
• 用 $current\_gold$ 更新答案。
• 尝试向四个方向递归搜索。
• 回溯：取消 $(i, j)$ 的访问标记。

第 3 步：返回最大黄金数。

4. 结合示例走一遍

$grid = [[0,6,0],[5,8,7],[0,9,0]]$

从 $(1,1)=8$ 出发：

• $(1,1) → (0,1)=6$（死胡同，总和 $14$）
• $(1,1) → (1,0)=5$（死胡同，总和 $13$）
• $(1,1) → (1,2)=7 → (2,2)=0$ 不能走，死胡同，总和 $15$）
• $(1,1) → (2,1)=9$（死胡同，总和 $17$）← 最大
• $(1,1) → (1,2)=7$ → 回溯后再试 $(2,1)=9$（但这需要从 $(1,2)$ 能到 $(2,1)$，不行因为 $(2,2)=0$）

最大为 $8+9=17$。

思路 1：代码

class Solution:
    def getMaximumGold(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        self.ans = 0

        def dfs(i: int, j: int, gold: int):
            # 收集当前格子的黄金
            gold += grid[i][j]
            self.ans = max(self.ans, gold)

            # 标记已访问（用临时置零来标记）
            val = grid[i][j]
            grid[i][j] = 0

            for di, dj in dirs:
                ni, nj = i + di, j + dj
                if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] > 0:
                    dfs(ni, nj, gold)

            # 回溯恢复
            grid[i][j] = val

        for i in range(m):
            for j in range(n):
                if grid[i][j] > 0:
                    dfs(i, j, 0)

        return self.ans

思路 1：复杂度分析

• 时间复杂度：$O(4^k)$，其中 $k$ 是非零格子的数量（$k \le 25$）。最坏情况下每步有 4 个选择，路径长度最多 $k$。但由于不能重复访问，实际搜索树远小于 $4^k$。
• 空间复杂度：$O(k)$，递归栈深度最多为路径长度，不超过 $k$。