算法leetcode

力扣1219-黄金矿工

字数统计: 1.1k字   |   阅读时长: 5分
,

摘要: 枚举所有起点的搜索题

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

本文我们来看一个搜索题，也是常见的在二维迷宫上按要求进行游走的问题。本题与其他常见问题不同的是迷宫中每个点作为起点都可能是最优解，因此需要枚举所有起点。

$1 题目

题目链接

1219. 黄金矿工

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

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

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

提示：

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

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

$2 题解

算法: 搜索

本题要求的是从某个起点出发，每个可访问点最多走一次的所有可能路线中，取得黄金的最大值。

固定了起点之后，我们可以 DFS 来枚举所有的可行路线，每条可行路线结束时，用所取得黄金的最大值更新答案。

因为 grid[i][j] = 0 的点不可以进入，且访问过的点也不可以进入，因此 grid 上是带有各个点是否可进入的信息的。

在某个起点对应的 DFS 中，因为 (i, j) 点黄金数信息 grid[i][j] 只有在当次 DFS 访问到该点 (i, j) 的时候才需要，之后就不需要了，因此可以直接修改 grid[i][j] = 0 作为该点已经访问的记录。

从 (i, j) 往下一个点走之前，先记录 grid[i][j] 的当前值，然后改为 0 传递给后续搜索路径。回溯之前再把 grid[i][j] 改为原来的值即可。

由于每个起点上都有可能产生最优解，因此需要枚举所有可能的起点进行 DFS。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
    int getMaximumGold(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        int ans = 0;
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < m; ++j)
            {
                if(grid[i][j] != 0)
                    ans = max(ans, solve(grid, i, j));
            }
        return ans;
    }

private:
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};

    int solve(vector<vector<int>>& grid, int i, int j)
    {
        // 以 (i, j) 起点，已经选 state 能取到的最大
        int n = grid.size(), m = grid[0].size();
        int mx = 0;
        int tmp = grid[i][j];
        grid[i][j] = 0;
        for(int d = 0; d < 4; ++d)
        {
            int x = i + dx[d], y = j + dy[d];
            if(x < 0 || x >= n || y < 0 || y >= m)
                continue;
            if(grid[x][y] == 0)
                continue;
            mx = max(mx, solve(grid, x, y));
        }
        grid[i][j] = tmp;
        return mx + grid[i][j];
    }
};

代码(Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution:
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]

    def getMaximumGold(self, grid: List[List[int]]) -> int:
        self.grid = grid
        n = len(grid)
        m = len(grid[0])
        ans = 0
        for i in range(n):
            for j in range(m):
                if grid[i][j] == 0:
                    continue
                ans = max(ans, self.dfs(i, j))
        return ans

    def dfs(self, i: int, j: int) -> int:
        n = len(self.grid)
        m = len(self.grid[0])
        max_ = 0
        tmp = self.grid[i][j]
        self.grid[i][j] = 0
        for d in range(4):
            x = i + self.__class__.dx[d]
            y = j + self.__class__.dy[d]
            if x < 0 or x >= n or y < 0 or y >= m:
                continue
            if self.grid[x][y] == 0:
                continue
            max_ = max(max_, self.dfs(x, y))
        self.grid[i][j] = tmp
        return max_ + self.grid[i][j]
Share