【递归算法】黄金矿工

文章摘要：

• 本文介绍了LeetCode 1219题"黄金矿工"的解题思路。题目要求在给定的m×n网格中，按照特定规则开采黄金，寻找收益最大的路径。文章详细解析了题目要求，通过示例展示了决策过程，并提出了基于深度优先搜索(DFS)的解决方案。算法使用回溯法遍历所有可能的开采路径，维护全局变量记录最大值。代码实现中包含了网格遍历、DFS函数设计、回溯处理和边界条件判断等关键步骤，最终返回所有路径中的最大黄金收益。该解法时间复杂度为O(mn*4^k)，其中k为路径平均长度。

题目链接：1219. 黄金矿工

一、题目解析

你要开发一座金矿，地质勘测学家已经探明了这座金矿中的资源分布，并用大小为 m * n 的网格 grid 进行了标注。每个单元格中的整数就表示这一单元格中的黄金数量；如果该单元格是空的，那么就是 0。为了使收益最大化，矿工需要按以下规则来开采黄金：

1. 每当矿工进入一个单元，就会收集该单元格中的所有黄金。
2. 矿工每次可以从当前位置向上下左右四个方向走。
3. 每个单元格只能被开采（进入）一次。
4. 不得开采（进入）黄金数目为 0 的单元格。
5. 矿工可以从网格中 任意一个 有黄金的单元格出发或者是停止

题目大致意思就是给出一个m x n的二维网格矩阵 grid，每一个单元格有数字，我们需要找到和最大的一条路径并返回这个和。

例如：

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

则 grid 表示的二维网格矩阵如下：

我们需要找到和最大的一条路径，大致如下：

1. 先从 6 开始，其上方越界，且左右均为 0，因此往下走到 8，此时的和为 14；在 8 这个位置有三个分支 5、7 和 9，分别都会得到结果19、21和23。此时从 6 开始的路线已全部搜索完了。
2. 然后从 5 开始，这时候，其左方越界，且上下均为 0，因此往右走到 8，此时的和为 13；在 8 这个位置同样会得到三个分支对应的结果 19、20和22。此时从 5 开始的路线已全部搜索完了。
3. 接着从 8 开始，这时候，其上下左右均有分支，会得到四个分支对应的结果14、17、13和15。此时从 8 开始的路线已全部搜索完了。
4. 然后从 7 开始，这时候，其右方越界，且上下均为 0，因此往左走到 8，此时的和为 15；在 8 这个位置同样会得到三个分支对应的结果 21、20 和24。此时从 7 开始的路线已全部搜索完了。
5. 最后 9 开始，其下方越界，且左右均为 0，因此往上走到 8，此时的和为 17；在 8 这个位置同样会得到三个分支对应的结果 22、23 和 24。此时从 9 开始的路线已全部搜索完了。

在上面得到的所有的结果中找到最大值然后返回即可，最大值是 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){grid=givenGrid;m=grid.length;n=grid[0].length;visit=newboolean[m][n];// 遍历矩阵for(inti=0;i<m;i++){for(intj=0;j<n;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){// 更新结果ret=Math.max(ret,count);for(intk=0;k<4;k++){intx=row+dx[k],y=col+dy[k];if(x>=0&&x<m&&y>=0&&y<n){if(grid[x][y]!=0&&!visit[x][y]){visit[x][y]=true;dfs(x,y,count+grid[x][y]);visit[x][y]=false;}}}}}

文章到这里就告一段落啦，若有错误请尽管指出~
完