Medium

题目描述

在一个大小为 m x n 的金矿网格中，每个单元格中的整数就是这个单元格中的黄金数量，如果该单元格是空的，那么就是 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。

提示：

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

解题思路

这是一道典型的回溯算法题目。由于我们可以从任意有黄金的位置开始，并且需要找到能获得最大黄金数量的路径，因此需要尝试所有可能的起始位置和路径。

解题思路：

  1. 暴力枚举起点：遍历网格中的每个单元格，对于每个有黄金的单元格，都将其作为起始点进行深度优先搜索。

  2. DFS + 回溯：从当前位置开始，尝试向四个方向（上下左右）移动。对于每个方向，如果目标位置合法（在边界内、有黄金、未访问过），就继续递归搜索。

  3. 状态标记与恢复：为了避免重复访问同一个单元格，在访问时将该位置标记为已访问（可以将值临时设为0），在回溯时恢复原值。

  4. 最优解更新：每次DFS返回当前路径能收集到的最大黄金数，不断更新全局最优解。

优化点：

  • 由于最多只有25个含金单元格，搜索空间相对较小
  • 使用原地标记避免额外的visited数组
  • 剪枝：如果当前路径已经无法超越已知最优解，可以提前返回

时间复杂度主要取决于有效路径的数量，在最坏情况下需要遍历所有可能的路径组合。

代码实现

class Solution {
public:
    int getMaximumGold(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        int maxGold = 0;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] > 0) {
                    maxGold = max(maxGold, dfs(grid, i, j));
                }
            }
        }
        
        return maxGold;
    }
    
private:
    int dfs(vector<vector<int>>& grid, int row, int col) {
        if (row < 0 || row >= grid.size() || col < 0 || col >= grid[0].size() || grid[row][col] == 0) {
            return 0;
        }
        
        int originalGold = grid[row][col];
        grid[row][col] = 0; // 标记为已访问
        
        int maxFromHere = originalGold + max({
            dfs(grid, row - 1, col), // 上
            dfs(grid, row + 1, col), // 下
            dfs(grid, row, col - 1), // 左
            dfs(grid, row, col + 1)  // 右
        });
        
        grid[row][col] = originalGold; // 回溯，恢复原值
        
        return maxFromHere;
    }
};

class Solution:
    def getMaximumGold(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        max_gold = 0
        
        def dfs(row, col):
            if row < 0 or row >= m or col < 0 or col >= n or grid[row][col] == 0:
                return 0
            
            original_gold = grid[row][col]
            grid[row][col] = 0  # 标记为已访问
            
            max_from_here = original_gold + max(
                dfs(row - 1, col),  # 上
                dfs(row + 1, col),  # 下
                dfs(row, col - 1),  # 左
                dfs(row, col + 1)   # 右
            )
            
            grid[row][col] = original_gold  # 回溯，恢复原值
            
            return max_from_here
        
        for i in range(m):
            for j in range(n):
                if grid[i][j] > 0:
                    max_gold = max(max_gold, dfs(i, j))
        
        return max_gold

public class Solution {
    public int GetMaximumGold(int[][] grid) {
        int m = grid.Length, n = grid[0].Length;
        int maxGold = 0;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] > 0) {
                    maxGold = Math.Max(maxGold, Dfs(grid, i, j));
                }
            }
        }
        
        return maxGold;
    }
    
    private int Dfs(int[][] grid, int row, int col) {
        if (row < 0 || row >= grid.Length || col < 0 || col >= grid[0].Length || grid[row][col] == 0) {
            return 0;
        }
        
        int originalGold = grid[row][col];
        grid[row][col] = 0; // 标记为已访问
        
        int maxFromHere = originalGold + Math.Max(Math.Max(
            Dfs(grid, row - 1, col), // 上
            Dfs(grid, row + 1, col)  // 下
        ), Math.Max(
            Dfs(grid, row, col - 1), // 左
            Dfs(grid, row, col + 1)  // 右
        ));
        
        grid[row][col] = originalGold; // 回溯，恢复原值
        
        return maxFromHere;
    }
}

var getMaximumGold = function(grid) {
    const m = grid.length, n = grid[0].length;
    let maxGold = 0;
    
    function dfs(row, col) {
        if (row < 0 || row >= m || col < 0 || col >= n || grid[row][col]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(k × 4^k)，其中 k 是含金单元格的数量（最多25个）。每个单元格作为起点时，最坏情况下需要探索 4^k 条路径
空间复杂度O(k)，递归调用栈的深度最多为 k（所有含金单元格都在一条路径上的情况）