友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
675. 为高尔夫比赛砍树
你被请来给一个要举办高尔夫比赛的树林砍树。树林由一个 m x n 的矩阵表示， 在这个矩阵中：
-
0表示障碍，无法触碰 -
1表示地面，可以行走 -
比 1 大的数表示有树的单元格，可以行走，数值表示树的高度
每一步，你都可以向上、下、左、右四个方向之一移动一个单位，如果你站的地方有一棵树，那么你可以决定是否要砍倒它。
你需要按照树的高度从低向高砍掉所有的树，每砍过一颗树，该单元格的值变为 1（即变为地面）。
你将从 (0, 0) 点开始工作，返回你砍完所有树需要走的最小步数。如果你无法砍完所有的树，返回 -1。
可以保证的是，没有两棵树的高度是相同的，并且你至少需要砍倒一棵树。
示例 1：
输入：forest = [[1,2,3],[0,0,4],[7,6,5]] 输出：6 解释：沿着上面的路径，你可以用 6 步，按从最矮到最高的顺序砍掉这些树。
示例 2：
输入：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 <= m, n <= 50 -
0 <= forest[i][j] <= 109
思路分析
翻译一下题目：从“原点”开始，逐步通过最短路径向上攀爬，直达封顶。这个过程的步数就是题目答案。
-
一刷
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
61
62
63
64
65
66
67
68
69
70
71
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2026-05-04 20:58:57
*/
int m;
int n;
int[][] dict = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
public int cutOffTree(List<List<Integer>> forest) {
m = forest.size();
n = forest.getFirst().size();
Queue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[2]));
for (int r = 0; r < m; r++) {
List<Integer> row = forest.get(r);
for (int c = 0; c < n; c++) {
if (row.get(c) > 1) {
pq.offer(new int[]{r, c, row.get(c)});
}
}
}
pq.offer(new int[]{0, 0, 1});
int result = 0;
int[] prev = pq.poll();
while (!pq.isEmpty()) {
int[] curr = pq.poll();
int step = find(prev[0], prev[1], curr[0], curr[1], forest, new boolean[m][n]);
if (step == -1) {
return -1;
}
result += step;
prev = curr;
}
return result;
}
private int find(int px, int py, int cx, int cy,
List<List<Integer>> forest, boolean[][] visited) {
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{px, py});
int step = 0;
while (!queue.isEmpty()) {
int size = queue.size();
while (size-- > 0) {
int[] curr = queue.poll();
if (visited[curr[0]][curr[1]]) {
continue;
}
visited[curr[0]][curr[1]] = true;
if (curr[0] == cx && curr[1] == cy) {
return step;
}
for (int i = 0; i < dict.length; i++) {
int dx = curr[0] + dict[i][0];
int dy = curr[1] + dict[i][1];
if (check(dx, dy, forest, visited)) {
queue.offer(new int[]{dx, dy});
}
}
}
step++;
}
return -1;
}
private boolean check(int dx, int dy, List<List<Integer>> forest, boolean[][] visited) {
return dx >= 0 && dx < forest.size()
&& dy >= 0 && dy < forest.get(dx).size()
&& !visited[dx][dy]
&& forest.get(dx).get(dy) > 0;
}