【解析与反思】leetcode 1219. 黄金矿工 DFS 解法（C++）

目录

前言

本文采用 DFS 算法求解问题，针对提交过程中遇到了超时的问题做出了分析和调试，供大家参考。

一、原题

你要开发一座金矿，地质勘测学家已经探明了这座金矿中的资源分布，并用大小为 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。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/path-with-maximum-gold
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二、基本思想

1. 找到所有的可开始的单元作为起点 start；

2. 每个 start 点开始【遍历挖矿】，最后比较哪种收集黄金最多；

3. 【遍历挖矿】其实是做 DFS 深度优先搜索，条件是：上下左右四个方向 && 不为0 && 未访问过的邻接点；

4. 遍历时同时求路线最大值；

5. 遍历完返回该点遍历后的最大路线值。

三、代码实现

1. 程序主体

首先，为了方便接下来的 DFS 方便访问 grid，在功能函数外创建了 public 下的 grid2 拷贝；

两层循环寻找每一个不为 0 的 start 点，将这些点进行 DFS 遍历；

DFS 遍历后的返回值更新目前的最大值 max；

因为 visit 定义在了外部，对当前 start 点访问完后需要重置回 0，即未访问状态，这样不影响下一个 start 点正常遍历；（还原，再探索其他情况）

class Solution {
public:
    int dir[4] = {0, 1, 0, -1};
    int visit[20][20] = {0};
    vector<vector<int>> grid2;

    int getMaximumGold(vector<vector<int>>& grid) {
        grid2 = grid;
        int n = grid.size();//row
        //if(!grid.empty()) 
        int m = grid.front().size();//array
        //to mark whether it's visited
        int max = 0;
        for(int i = 0; i < n; i ++){
            for(int j = 0; j < m; j++){
                if(grid[i][j]){
                    visit[i][j] = 1;
                    max = max < DFS(i,j)? DFS(i,j): max;
                    visit[i][j] = 0;
                }
            }
        }
        return max;
    }
};

2. DFS 接着在 public 下定义

本题的 DFS 比基本 DFS 多以下几个问题：

• 上下左右四个方向邻接点如何表示
• 如何在遍历的过程中加和返回【最佳路径值】

解析：

• 上下左右：
  分析共（i,j+1）（i,j-1）（i+1,j）（i-1,j）四个点，发现规律 i ± 1 的时候，j 是不变的；同样 j ± 1 的时候，i 是不变的。
  因此创建 0，±1 交错的数组 dir[4] = {0, 1, 0, -1}，利用 k 遍历数组，让 i + dir[k]，j + dir[k+1]，为了让 dir[k+1] 能成环，所以对于 j 用取余的方法访问 dir[]；所以让 j + dir[(k+1)%4]。
• 加和 ans：
  首先 ans 必定包含非 0 start 点的值，故初始化为 grid[i][j];
  访问符合条件的邻接点时，我们期望 ans 加上邻接点中【子线路】的值 再 加上该邻接点的值，因此构成递归解决问题；
  若该邻接点 【子线路】的值 再 加上该邻接点的值 没有现在 ans 大，则不选择该路线，也不会更新 ans；
  而递归的终点即最后一个点，该点无符合要求的邻接点，故 ans = grid[终点][终点]，返回初始化的值即可；

    int DFS(int i, int j){
        int ans = grid2[i][j];
        //4 cells around
         for (int k = 0; k < 4; k++){
            int x = i + dir[k], y = j + dir[(k + 1) % 4];
            if(x < 0 || x >= grid2.size() || y < 0 || y >= grid2.front().size() || !grid2[x][y] || visit[x][y]) continue;
            visit[x][y] = 1;
            ans = ans < DFS(x, y) + grid2[i][j] ? DFS(x, y)+ grid2[i][j]:ans;
            visit[x][y] = 0;
        }
        return ans;
    }

四、代码优化

然而天有不测风雨...代码超时了。

在多次排查后发现罪魁祸首是 DFS 中的：

ans = ans < DFS(x, y) + grid2[i][j] ? DFS(x, y)+ grid2[i][j]:ans;

这里判断语句快速返回值中，每书写一次 DFS，都会做一次递归，因此时间炸了，功能函数中只有 1 次所以速度不影响。

改进-> 记录下 DFS 的值即可

所以我用的：

ans = max(ans, DFS(x, y) + grid2[i][j]);

就过了。

五、Dijktra 算法思考

问题可以同样转化成有权图的单源最长路算法。

回头填坑。