## 题目描述 你要开发一座金矿，地质勘测学家已经探明了这座金矿中的资源分布，并用大小为 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。 ``` ### 题目解答 #### 思路 **回溯法** 遍历$$x \times y$$个方格，如果该方格$$grid \neq 0$$, 那么可以从该点开始，采用dfs进行遍历，需按照该点开始最大采矿数值。 **复杂度** - 1 <= grid.length, grid[i].length <= 15 - 0 <= grid[i][j] <= 100 - 最多 25 个单元格中有黄金。 设grid长宽为m和n，有黄金的格子数量T，需要对T个格子开始进行枚举, 时间复杂度为$$O(T)$$ 对于每个格子，下一步通常有3个方向可以选择，因此选定开始路线之后，该路线上复杂度为$$O(3^T)$$ 因此，整体的时间复杂度为$$O(T \times 3^T)$$ #### 代码实现 ```java class Solution { // 记录每个格子开始dfs中开始的最大值 public int max = 0; // 遍历每个格子，用max_val记录每个格子开始的最大值 public int getMaximumGold(int[][] grid) { int max_val = 0; for(int i=0;i<grid.length;i++){ for(int j=0;j<grid[0].length;j++){ dfs(grid, i, j, 0); if(max > max_val){ max_val = max; } max = 0;//将该格子dfs值清空 } } return max_val; } // 从i，j开始，在已获得val的基础上再进行开采 public void dfs(int[][] grid, int i, int j, int val){ // 如果越界或者该位置不可开采，说明已经到头，比较最大值返回 if(i<0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j]==0){ if(val > max){ max = val; } return; } // 如果可以开采的话，记录该位置val，并且将其设0，代表已经开采 int tmp = grid[i][j]; grid[i][j] = 0; // 四个方向遍历 dfs(grid, i+1, j, val+tmp); dfs(grid, i-1, j, val+tmp); dfs(grid, i, j+1, val+tmp); dfs(grid, i, j-1, val+tmp); // 完成后将该处数值返回 grid[i][j] = tmp; } } ``` 最后编辑：2024年04月23日 ©著作权归作者所有 赞 0 分享
最新回复