黄金矿工 图解题解

这道题到底在问什么

输入

[[0,6,0],[5,8,7],[0,9,0]]

输出

24（路径 9 → 8 → 7）

最优解：一步一步想明白

1. 3记住「踩格记金 → 置 0 标记 → 四向取最大 → 退格还原」。下面在官方样例上，从黄金 9 这个起点一步步走。
2. 4先扫一遍：网格里一共 5 个有黄金的格(土黄底色，可踩)，写 0 的是空格(灰底，不能进)。题目允许从任意金格出发，所以每个金格都要各当一次起点试一遍。
3. 5这里挑收益最高的起点 黄金 9（紫色）演示整条 DFS 搜索，看它一路能挖到多少黄金。
4. 6踩进格子 (2,1)，挖到黄金 9：把它临时置 0（紫色 = 正踩、黄色 = 路径已占用），本趟这格不能再进。当前路径金子累计 9，继续往没踩过的邻居探。
5. 7踩进格子 (1,1)，挖到黄金 8：把它临时置 0（紫色 = 正踩、黄色 = 路径已占用），本趟这格不能再进。当前路径金子累计 17，继续往没踩过的邻居探。
6. 8踩进格子 (0,1)，挖到黄金 6：把它临时置 0（紫色 = 正踩、黄色 = 路径已占用），本趟这格不能再进。当前路径金子累计 23，继续往没踩过的邻居探。
7. 9格子 (0,1) 的上下左右要么是空格 0、要么已被本趟踩过，无路可走。这条分支到此结束，它能贡献的黄金就是路径上的 6，准备回溯。
8. 10从 (0,1) 退出：把它的金子 6 还原回去（撤销那个置 0 的标记），这样别的走法还能踩到它。退回上一格，继续试它下一个方向。
9. 11踩进格子 (1,2)，挖到黄金 7：把它临时置 0（紫色 = 正踩、黄色 = 路径已占用），本趟这格不能再进。当前路径金子累计 24，继续往没踩过的邻居探。
10. 12格子 (1,2) 的上下左右要么是空格 0、要么已被本趟踩过，无路可走。这条分支到此结束，它能贡献的黄金就是路径上的 7，准备回溯。
11. 13从 (1,2) 退出：把它的金子 7 还原回去（撤销那个置 0 的标记），这样别的走法还能踩到它。退回上一格，继续试它下一个方向。
12. 14踩进格子 (1,0)，挖到黄金 5：把它临时置 0（紫色 = 正踩、黄色 = 路径已占用），本趟这格不能再进。当前路径金子累计 22，继续往没踩过的邻居探。
13. 15格子 (1,0) 的上下左右要么是空格 0、要么已被本趟踩过，无路可走。这条分支到此结束，它能贡献的黄金就是路径上的 5，准备回溯。
14. 16从 (1,0) 退出：把它的金子 5 还原回去（撤销那个置 0 的标记），这样别的走法还能踩到它。退回上一格，继续试它下一个方向。
15. 17格 (1,1) 的四个方向都试完了，里面最大的一条分支贡献 7。于是本格能挖的黄金 = 自己的 8 + 最大分支 7 = 15，把这个值往上一层返回。
16. 18格 (2,1) 的四个方向都试完了，里面最大的一条分支贡献 15。于是本格能挖的黄金 = 自己的 9 + 最大分支 15 = 24，把这个值往上一层返回。
17. 19刚才只是其中一个起点。换从顶上的 黄金 6(紫色)出发，把它当起点再跑一遍 DFS，看能不能挖得比 24 更多。
18. 20踩进 (1,1)，挖到黄金 8，这条路累计 14。继续往下探。
19. 21踩进 (2,1)，挖到黄金 9，这条路累计 23。它在底行，四周已经没有能继续接上的金格了，这条路到此为止，准备结算。
20. 22从 6 出发最多挖到 6 + 8 + 9 = 23，比之前从 9 出发的 24 还少 1，所以不刷新答案。这就是「每个金格都当起点、取所有结果最大值」的意义。
21. 23从黄金 9 出发的这条线，9 → 8 → 7（绿色）收集到 9 + 8 + 7 = 24 黄金。把每个金格各当起点跑一遍后，没有比它更高的，所以答案是 24。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from typing import List
class Solution:
    def getMaximumGold(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        def dfs(r, c):
            if r < 0 or r >= m or c < 0 or c >= n or grid[r][c] == 0:
                return 0
            gold = grid[r][c]
            grid[r][c] = 0
            best = max(dfs(r+1,c), dfs(r-1,c), dfs(r,c+1), dfs(r,c-1))
            grid[r][c] = gold
            return gold + best
        return max(dfs(r, c) for r in range(m) for c in range(n))

#include <vector>
#include <functional>
#include <algorithm>
using namespace std;
class Solution {
public:
    int getMaximumGold(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        function<int(int,int)> dfs = [&](int r, int c) {
            if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] == 0) return 0;
            int gold = grid[r][c];
            grid[r][c] = 0;
            int best = max(max(dfs(r+1,c), dfs(r-1,c)), max(dfs(r,c+1), dfs(r,c-1)));
            grid[r][c] = gold;
            return gold + best;
        };
        int ans = 0;
        for (int r = 0; r < m; ++r) for (int c = 0; c < n; ++c) ans = max(ans, dfs(r, c));
        return ans;
    }
};

import java.util.*;
class Solution {
    int[][] grid; int m, n;
    public int getMaximumGold(int[][] grid) {
        this.grid = grid; m = grid.length; n = grid[0].length;
        int ans = 0;
        for (int r = 0; r < m; r++) for (int c = 0; c < n; c++) ans = Math.max(ans, dfs(r, c));
        return ans;
    }
    private int dfs(int r, int c) {
        if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] == 0) return 0;
        int gold = grid[r][c]; grid[r][c] = 0;
        int best = Math.max(Math.max(dfs(r+1,c), dfs(r-1,c)), Math.max(dfs(r,c+1), dfs(r,c-1)));
        grid[r][c] = gold;
        return gold + best;
    }
}

复杂度

面试官可能追问