黄金矿工 | 徐年の博客

力扣 1219. 黄金矿工

题目说明

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

为了使收益最大化，矿工需要按以下规则来开采黄金：

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

提示：

1 <= grid.length, grid[i].length <= 15
0 <= grid[i][j] <= 100
最多 25 个单元格中有黄金。

示例

示例 1:

1
2
3

输入：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。

笔者理解

此题是一道数组算法问题，在力扣题库中被定义为中等题。

解法

当笔者阅读完此题后，发现此题很经典得DFS，按部就班即可，让我们来看看具体如何实现的吧。

实现

class Solution {
    /**
     * DFS
     */

    int result, row, column;

    // 转向位移
    int[] turnX = {-1, 1, 0, 0};
    int[] turnY = {0, 0, -1, 1};

    public int getMaximumGold(int[][] grid) {
        row = grid.length;
        column = grid[0].length;

        // 标记是否走过
        boolean[][] ticks = new boolean[row][column];
        result = 0;

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < column; j++) {
                if (grid[i][j] != 0) {
                    ticks[i][j] = true;
                    dfs(grid, ticks, i, j, grid[i][j]);
                    ticks[i][j] = false;
                }
            }
        }

        return result;
    }

    /**
     * dfs
     *
     * @param grid  单元格
     * @param ticks 标记
     * @param x0    x0
     * @param y0    y0
     * @param count 黄金数
     */
    public void dfs(int[][] grid, boolean[][] ticks, int x0, int y0, int count) {
        boolean isTurn = false;

        for (int i = 0; i < 4; i++) {
            int x = x0 + turnX[i];
            int y = y0 + turnY[i];

            if (judge(x, y) && grid[x][y] != 0 && !ticks[x][y]) {
                isTurn = true;
                ticks[x][y] = true;
                dfs(grid, ticks, x, y, count + grid[x][y]);
                ticks[x][y] = false;
            }
        }

        if (!isTurn) {
            result = Math.max(result, count);
        }
    }

    /**
     * 判断当前坐标是否越界
     *
     * @param x x
     * @param y y
     * @return boolean
     */
    public boolean judge(int x, int y) {
        return x >= 0 && y >= 0 && (x - row) * (y - column) > 0;
    }
}