0%

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

题目

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 ♥ ---

欢迎关注我呀~