小鲸鱼的梦境
0%

『LeetCode』675 为高尔夫比赛砍树

发表于 分类于 Valine：
本文字数： 4.6k 阅读时长 ≈ 4 分钟

题目

675. 为高尔夫比赛砍树

你被请来给一个要举办高尔夫比赛的树林砍树。树林由一个 m x n 的矩阵表示， 在这个矩阵中：

  • 0 表示障碍，无法触碰
  • 1 表示地面，可以行走
  • 比 1 大的数 表示有树的单元格，可以行走，数值表示树的高度

每一步，你都可以向上、下、左、右四个方向之一移动一个单位，如果你站的地方有一棵树，那么你可以决定是否要砍倒它。

你需要按照树的高度从低向高砍掉所有的树，每砍过一颗树，该单元格的值变为 1（即变为地面）。

你将从 (0, 0) 点开始工作，返回你砍完所有树需要走的最小步数。 如果你无法砍完所有的树，返回 -1 。

可以保证的是，没有两棵树的高度是相同的，并且你至少需要砍倒一棵树。

示例 1：

trees1

输入：forest = [[1,2,3],[0,0,4],[7,6,5]]
输出：6
解释：沿着上面的路径，你可以用 6 步，按从最矮到最高的顺序砍掉这些树。

示例 2：

trees2

输入：forest = [[1,2,3],[0,0,0],[7,6,5]]
输出：-1
解释：由于中间一行被障碍阻塞，无法访问最下面一行中的树。

示例 3：

输入：forest = [[2,3,4],[0,0,5],[8,7,6]]
输出：6
解释：可以按与示例 1 相同的路径来砍掉所有的树。
(0,0) 位置的树，可以直接砍去，不用算步数。

提示：

  • \(m == forest.length\)
  • \(n == forest[i].length\)
  • \(1 \leq m, n \leq 50\)
  • \(0 \leq forest[i][j] \leq 10^{9}\)

题解

【为高尔夫比赛砍树】BFS

BFS

注意到树的高度唯一，这很关键，因为如果树的高度不唯一，那么砍树路径就会有很多选择，问题会复杂得多。所以实际上题目的要求就等价于按顺序访问图中的结点，同时不能碰到障碍物。

可以使用简单的 bfs 访问，或者 dijkstra 计算。

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
39
# Code language: Python
class Solution:
    def cutOffTree(self, forest: List[List[int]]) -> int:
        n, m = len(forest), len(forest[0])

        order = [(h, x, y) for x, row in enumerate(forest) for y, h in enumerate(row) if h > 1]
        order.sort()

        dirs = ((0, 1), (0, -1), (1, 0), (-1, 0))
        def walk(cur, target):
            """ BFS """
            if cur == target: return 0
            d = deque([cur])
            vis = set()
            step = 0
            while d:
                for _ in range(len(d)):
                    x, y = d.popleft()
                    for i, j in dirs:
                        dx, dy = x + i, y + j
                        if dx < 0 or dx >= n or dy < 0 or dy >= m or forest[dx][dy] == 0:
                            continue
                        if (dx, dy) == target:
                            return step + 1
                        if (dx, dy) not in vis:
                            d.append((dx, dy))
                            vis.add((dx, dy))
                step += 1
            return -1
            
        cur = (0, 0)
        ans = 0
        for h, x, y in order:
            step = walk(cur, (x, y))
            if step == -1:
                return -1
            ans += step
            cur = (x, y)
        return ans
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
// Code language: Java
class Solution {
    static int[] vis = new int[5555];
    static int[][] dirs = new int[][] { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };

    public int cutOffTree(List<List<Integer>> forest) {
        int n = forest.size(), m = forest.get(0).size();
        List<int[]> order = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (forest.get(i).get(j) > 1)
                    order.add(new int[] { forest.get(i).get(j), i, j });
            }
        }
        Collections.sort(order, (a, b) -> a[0] - b[0]);

        int x = 0, y = 0, ans = 0;
        for (int[] cur : order) {
            int nx = cur[1], ny = cur[2];
            int step = walk(forest, x, y, nx, ny);
            if (step == -1)
                return -1;
            ans += step;
            x = nx;
            y = ny;
        }
        return ans;
    }

    public int walk(List<List<Integer>> forest, int x, int y, int target_x, int target_y) {
        // BFS
        if (x == target_x && y == target_y)
            return 0;
        int n = forest.size(), m = forest.get(0).size();
        Deque<Integer> d = new ArrayDeque<>();
        d.addLast(x * 100 + y);
        Arrays.fill(vis, 0);
        int step = 0;
        while (!d.isEmpty()) {
            for (int i = 0, s = d.size(); i < s; ++i) {
                int cur = d.pollFirst();
                int cx = cur / 100, cy = cur % 100;
                for (int[] nxt : dirs) {
                    int dx = cx + nxt[0], dy = cy + nxt[1];
                    if (dx < 0 || dx >= n || dy < 0 || dy >= m || forest.get(dx).get(dy) == 0)
                        continue;
                    if (dx == target_x && dy == target_y)
                        return step + 1;
                    int key = dx * 100 + dy;
                    if (vis[key] == 0) {
                        d.addLast(key);
                        vis[key] = 1;
                    }
                }
            }
            step++;
        }
        return -1;
    }
}
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
// Code language: Cpp
using VI = vector<int>;
using VII = vector<VI>;
using PII = pair<int, int>;
class Solution {
public:
    int vis[5555];
    VII dirs{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    int cutOffTree(vector<vector<int>>& forest) {
        int n = forest.size(), m = forest[0].size();
        vector<PII> order;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (forest[i][j] > 1)
                    order.push_back(PII{forest[i][j], i * 100 + j});
            }
        }
        sort(order.begin(), order.end());

        int x = 0, y = 0, ans = 0;
        for (PII& cur : order) {
            int nx = cur.second / 100, ny = cur.second % 100;
            int step = walk(forest, x, y, nx, ny);
            if (step == -1) return -1;
            ans += step;
            x = nx, y = ny;
        }
        return ans;
    }

    int walk(VII& forest, int x, int y, int target_x, int target_y) {
        // BFS
        if (x == target_x && y == target_y) return 0;
        int n = forest.size(), m = forest[0].size();
        deque<int> d;
        d.emplace_back(x * 100 + y);
        memset(vis, 0, sizeof(vis));
        int step = 0;
        while (!d.empty()) {
            for (int i = 0, s = d.size(); i < s; ++i) {
                int cur = d.front();
                int x = cur / 100, y = cur % 100;
                d.pop_front();
                for (VI& nxt : dirs) {
                    int dx = x + nxt[0], dy = y + nxt[1];
                    if (dx < 0 || dx >= n || dy < 0 || dy >= m || forest[dx][dy] == 0)
                        continue;
                    if (dx == target_x && dy == target_y) return step + 1;
                    int key = dx * 100 + dy;
                    if (vis[key] == 0) {
                        d.emplace_back(key);
                        vis[key] = 1;
                    }
                }
            }
            step++;
        }
        return -1;
    }
};
  • 时间复杂度: \(O(n^2m^2)\), 排序 \(O(nm \log (nm))\), 一次 BFS 上界是 \(O(nm)\), 最多进行 \(nm\) 次
  • 空间复杂度: \(O(nm)\)

两个优化方向

  1. 优化最短路算法，BFS 并非最优解
  2. 在图中多次查找两点的最短路，会有一些重复操作，是否可以通过记忆化或者其他方法优化呢？

下次有时间再补充吧~

--- ♥ end ♥ ---

欢迎关注我呀~