黄金矿工

难度: Medium

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

示例 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。

提示：

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

Submission

运行时间: 441 ms

内存: 16.1 MB

class Solution:
    def getMaximumGold(self, grid: List[List[int]]) -> int:
        res = 0
        b = set()
        g_x, g_y = len(grid[0]), len(grid)

        def backtrack(x, y, count, vis_local):
            nonlocal res
            if count > res:
                res = count
            for i, j in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                n_x, n_y = x + i, y + j
                if 0 <= n_x < g_x and 0 <= n_y < g_y and vis_local[n_y][n_x] and grid[n_y][n_x]:
                    vis_local[n_y][n_x] = 0
                    backtrack(n_x, n_y, count + grid[n_y][n_x], vis_local)
                    vis_local[n_y][n_x] = 1

        def find_corner(i, j):
            count = 0
            for x, y in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                n_x, n_y = x + i, y + j
                if 0 <= n_x < g_x and 0 <= n_y < g_y and grid[n_y][n_x]:
                    count += 1
            return count <= 2

        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] and find_corner(j, i):
                    print(i, j)
                    vis_local = [[1] * g_x for _ in range(g_y)]
                    vis_local[i][j] = 0
                    backtrack(j, i, grid[i][j], vis_local)
        return res


# 作者：时雨
# 链接：https://leetcode.cn/problems/path-with-maximum-gold/solutions/1243095/ji-bai-100-python-hui-su-you-hua-by-driz-lpfv/
# 来源：力扣（LeetCode）
# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

Explain

该题解使用了回溯法来解决问题。首先，它定义了一个递归函数backtrack来尝试所有可能的路径，并使用一个局部变量vis_local来记录已经访问过的单元格，以避免重复访问。函数backtrack接受当前位置(x, y)和当前收集到的黄金总量count作为参数，它会尝试向四个方向探索，并在探索后回溯。此外，题解中还使用了一个函数find_corner来优化搜索过程，该函数用于判断一个单元格是否是一个'角落'，即最多只与两个有黄金的单元格相邻。如果一个单元格是角落，则可以从该单元格开始搜索，这样可以减少不必要的搜索次数。

时间复杂度: O(4^(mn))

空间复杂度: O(mn)

class Solution:
    def getMaximumGold(self, grid: List[List[int]]) -> int:
        res = 0
        b = set()
        g_x, g_y = len(grid[0]), len(grid)

        def backtrack(x, y, count, vis_local):
            nonlocal res
            if count > res:
                res = count
            for i, j in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                n_x, n_y = x + i, y + j
                if 0 <= n_x < g_x and 0 <= n_y < g_y and vis_local[n_y][n_x] and grid[n_y][n_x]:
                    vis_local[n_y][n_x] = 0
                    backtrack(n_x, n_y, count + grid[n_y][n_x], vis_local)
                    vis_local[n_y][n_x] = 1

        def find_corner(i, j):
            count = 0
            for x, y in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                n_x, n_y = x + i, y + j
                if 0 <= n_x < g_x and 0 <= n_y < g_y and grid[n_y][n_x]:
                    count += 1
            return count <= 2

        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] and find_corner(j, i):
                    vis_local = [[1] * g_x for _ in range(g_y)]
                    vis_local[i][j] = 0
                    backtrack(j, i, grid[i][j], vis_local)
        return res

# 作者：时雨
# 链接：https://leetcode.cn/problems/path-with-maximum-gold/solutions/1243095/ji-bai-100-python-hui-su-you-hua-by-driz-lpfv/
# 来源：力扣（LeetCode）
# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

Explore

在回溯算法中使用一个局部变量vis_local而不直接修改grid数组的主要原因是为了保护原始数据。使用vis_local可以帮助我们跟踪在特定递归路径中哪些单元格已经被访问过，而不改变grid本身，这样在回溯到上一层的时候可以很容易地通过修改vis_local的状态来'撤销'访问，恢复到上一状态。如果直接修改grid，那么每次访问后都需要恢复原始值，这不仅增加了操作的复杂度，还可能引入错误，特别是在多线程或需要频繁读取原始数据的情况下。

find_corner函数通过检查一个单元格最多只与两个有黄金的单元格相邻来判断它是否是角落。这个逻辑虽然可以帮助减少搜索次数和避免从中间位置非必要的搜索，但它确实可能导致一些潜在的良好起点被忽略，特别是那些虽然不是传统意义上的'角落'但起始位置可能导致高收益的单元格。因此，这种优化虽然可以提高效率，但可能牺牲了一定的全局最优解的搜索潜力。

在backtrack函数中，每次向一个方向探索前，都会先将当前单元格的访问状态在vis_local中设置为0（标记为已访问），然后递归调用探索该方向。探索完毕后，无论是找到了新的黄金还是没有更进一步的路径可走，都将当前单元格的vis_local状态重新设置为1（标记为未访问）。这种方法确保了每次探索完一个方向后都能够恢复到探索前的状态，使得算法能够正确地回溯到上一步，继续尝试其他可能的探索方向。这是回溯算法中常见的处理方式，有效地利用了递归栈的特性来管理状态的存储和恢复。