文章摘要本文介绍了LeetCode 1219题黄金矿工的解题思路。题目要求在给定的m×n网格中按照特定规则开采黄金寻找收益最大的路径。文章详细解析了题目要求通过示例展示了决策过程并提出了基于深度优先搜索(DFS)的解决方案。算法使用回溯法遍历所有可能的开采路径维护全局变量记录最大值。代码实现中包含了网格遍历、DFS函数设计、回溯处理和边界条件判断等关键步骤最终返回所有路径中的最大黄金收益。该解法时间复杂度为O(mn*4^k)其中k为路径平均长度。文章目录一、题目解析二、算法原理 代码实现决策树全局变量dfs 函数函数头函数体细节问题回溯剪枝递归出口代码实现题目链接1219. 黄金矿工一、题目解析你要开发一座金矿地质勘测学家已经探明了这座金矿中的资源分布并用大小为 m * n 的网格 grid 进行了标注。每个单元格中的整数就表示这一单元格中的黄金数量如果该单元格是空的那么就是 0。为了使收益最大化矿工需要按以下规则来开采黄金每当矿工进入一个单元就会收集该单元格中的所有黄金。矿工每次可以从当前位置向上下左右四个方向走。每个单元格只能被开采进入一次。不得开采进入黄金数目为 0 的单元格。矿工可以从网格中 任意一个 有黄金的单元格出发或者是停止题目大致意思就是给出一个m x n的二维网格矩阵 grid每一个单元格有数字我们需要找到和最大的一条路径并返回这个和。例如grid [ [ 0, 6, 0 ], [ 5, 8, 7 ], [ 0, 9, 0 ] ]则 grid 表示的二维网格矩阵如下060587090我们需要找到和最大的一条路径大致如下先从 6 开始其上方越界且左右均为 0因此往下走到 8此时的和为 14在 8 这个位置有三个分支 5、7 和 9分别都会得到结果19、21和23。此时从 6 开始的路线已全部搜索完了。然后从 5 开始这时候其左方越界且上下均为 0因此往右走到 8此时的和为 13在 8 这个位置同样会得到三个分支对应的结果 19、20和22。此时从 5 开始的路线已全部搜索完了。接着从 8 开始这时候其上下左右均有分支会得到四个分支对应的结果14、17、13和15。此时从 8 开始的路线已全部搜索完了。然后从 7 开始这时候其右方越界且上下均为 0因此往左走到 8此时的和为 15在 8 这个位置同样会得到三个分支对应的结果 21、20 和24。此时从 7 开始的路线已全部搜索完了。最后 9 开始其下方越界且左右均为 0因此往上走到 8此时的和为 17在 8 这个位置同样会得到三个分支对应的结果 22、23 和 24。此时从 9 开始的路线已全部搜索完了。060587090在上面得到的所有的结果中找到最大值然后返回即可最大值是 24因此返回 24对应的路径是 7 - 8 - 9 或者 9 - 8 - 7。二、算法原理 代码实现我们依旧采用暴搜的策略来解决只需要找出所有并分别统计对应的值找出最大值即可。决策树基于例子 grid [ [ 0, 6, 0 ], [ 5, 8, 7 ], [ 0, 9, 0 ] ]作出部分决策树如下全局变量我们需要一个与题目给出的二维数组相同大小的布尔数组visit用于标记每一个方格的访问状态同时在访问某个位置的上下左右四个方向时也需要两个向量数组dx和dy。为了递归时方便将题目给出的二维数组grid改为全局变量同时将m和n也改为全局变量一个整数ret用于记录结果。int[][] grid; boolean[][] visit; int m, n, ret; int[] dx {0, 0, -1, 1}; int[] dy {-1, 1, 0, 0};dfs 函数函数头我们给 dfs 函数设置的任务是基于所给位置向其四周扫描指定的元素这里我们需要提供某个位置的坐标。然后由于本题需要求和使用简单类型即可满足因此我们选择将这个用于统计和的变量count作为函数的参数之一。函数的返回值是 void 类型。dfs(int row, int col, int count);函数体我们只需要循环四次分别访问某位置的上、下、左和右即可然后确保不越界、符合要求即可。细节问题回溯由于求和的变量已设置为 dfs 函数的参数了可以依靠程序自动进行恢复现场的操作本题的回溯操作只需要对 visit 数组进行操作即可——将某位置的值修改回 false。剪枝本题采用了暴搜的解决方式因此不涉及到剪枝的操作。递归出口本题只需要把所有情况都列举出来列举完成之后自然就会结束递归因此无需递归出口。而对ret的更新我们需要放在 dfs 函数体中的开头因为我们若要判断叶子节点即不能再继续搜索了需要判断其上下左右均不能走这需要四个循环来判断为了提高效率我们选择维护 ret 这个变量。代码实现classSolution{int[][]grid;boolean[][]visit;intm,n,ret;int[]dx{0,0,-1,1};int[]dy{-1,1,0,0};publicintgetMaximumGold(int[][]givenGrid){gridgivenGrid;mgrid.length;ngrid[0].length;visitnewboolean[m][n];// 遍历矩阵for(inti0;im;i){for(intj0;jn;j){// 找到非0的方格, 以此为中心向四周扫描下一个非0if(grid[i][j]!0){visit[i][j]true;dfs(i,j,grid[i][j]);visit[i][j]false;// 回溯}}}returnret;}publicvoiddfs(introw,intcol,intcount){// 更新结果retMath.max(ret,count);for(intk0;k4;k){intxrowdx[k],ycoldy[k];if(x0xmy0yn){if(grid[x][y]!0!visit[x][y]){visit[x][y]true;dfs(x,y,countgrid[x][y]);visit[x][y]false;}}}}}文章到这里就告一段落啦若有错误请尽管指出~完