1219.黄金矿工

链接：1219.黄金矿工
难度：Medium
标签：数组、回溯、矩阵
简介：要开发一座金矿，地质勘测学家已经探明了这座金矿中的资源分布，并用大小为  m * n 的网格 grid 进行了标注。每个单元格中的整数就表示这一单元格中的黄金数量；如果该单元格是空的，那么就是 0。

题解 1 - cpp

• 编辑时间：2022-02-05
• 执行用时：580ms
• 内存消耗：169.2MB
• 编程语言：cpp
• 解法介绍：dfs。

int dirs[4][2] = {
    {0, 1},
    {0, -1},
    {1, 0},
    {-1, 0},
};
class Solution {
   public:
    int m, n, ans = 0;
    int getMaximumGold(vector<vector<int>>& grid) {
        m = grid.size();
        n = grid[0].size();
        vector<vector<int>> check(m, vector(n, 0));
        for (int row = 0; row < m; row++) {
            for (int col = 0; col < n; col++) {
                if (grid[row][col] == 0) continue;
                int cnt = 0;
                for (int i = 0; i < 4; i++) {
                    int nrow = row + dirs[i][0], ncol = col + dirs[i][1];
                    if (nrow >= 0 && nrow < m && ncol >= 0 && ncol < n &&
                        grid[nrow][ncol] != 0)
                        cnt++;
                }
                if (cnt < 3) dfs(grid, check, row, col, 0);
            }
        }
        return ans;
    }
    void dfs(vector<vector<int>>& grid, vector<vector<int>> check, int row,
             int col, int cur) {
        check[row][col] = 1;
        cur += grid[row][col];
        ans = max(ans, cur);
        for (int i = 0; i < 4; i++) {
            int nrow = row + dirs[i][0], ncol = col + dirs[i][1];
            if (nrow < 0 || nrow >= m || ncol < 0 || ncol >= n ||
                grid[nrow][ncol] == 0 || check[nrow][ncol] == 1)
                continue;
            dfs(grid, check, nrow, ncol, cur);
        }
        check[row][col] = 0;
    }
};