LeetCode 题解工作台
为高尔夫比赛砍树
你被请来给一个要举办高尔夫比赛的树林砍树。树林由一个 m x n 的矩阵表示， 在这个矩阵中： 0 表示障碍，无法触碰 1 表示地面，可以行走 比 1 大的数 表示有树的单元格，可以行走，数值表示树的高度 每一步，你都可以向上、下、左、右四个方向之一移动一个单位，如果你站的地方有一棵树，那么你可以决…
4
题型
5
代码语言
3
相关题
当前训练重点
困难 · 图·搜索
答案摘要
题目的一个关键信息是“所有树的高度都不同”，要按照从小到大的顺序依次砍树，因此，我们先遍历树林，找出所有树及对应的坐标点。然后将树按照高度升序排列。 接下来就是找相邻两个点之间的最短距离。可以用 BFS，A\* 算法优化搜索。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 图·搜索 题型思路
题目描述
你被请来给一个要举办高尔夫比赛的树林砍树。树林由一个 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.lengthn == forest[i].length1 <= m, n <= 500 <= forest[i][j] <= 109
解题思路
方法一：BFS + 优先队列（A* 算法）
题目的一个关键信息是“所有树的高度都不同”，要按照从小到大的顺序依次砍树，因此，我们先遍历树林，找出所有树及对应的坐标点。然后将树按照高度升序排列。
接下来就是找相邻两个点之间的最短距离。可以用 BFS，A* 算法优化搜索。
A* 算法主要思想如下：
- 将 BFS 队列转换为优先队列（小根堆）；
- 队列中的每个元素为
(dist[state] + f(state), state)，dist[state]表示从起点到当前 state 的距离，f(state)表示从当前 state 到终点的估计距离，这两个距离之和作为堆排序的依据； - 当终点第一次出队时，说明找到了从起点到终点的最短路径，直接返回对应的 step；
f(state)是估价函数，并且估价函数要满足f(state) <= g(state)，其中g(state)表示 state 到终点的真实距离；- A* 算法只能保证终点第一次出队时，即找到了一条从起点到终点的最小路径，不能保证其他点出队时也是从起点到当前点的最短路径。
class Solution:
def cutOffTree(self, forest: List[List[int]]) -> int:
def f(i, j, x, y):
return abs(i - x) + abs(j - y)
def bfs(i, j, x, y):
q = [(f(i, j, x, y), i, j)]
dist = {i * n + j: 0}
while q:
_, i, j = heappop(q)
step = dist[i * n + j]
if (i, j) == (x, y):
return step
for a, b in [[0, -1], [0, 1], [-1, 0], [1, 0]]:
c, d = i + a, j + b
if 0 <= c < m and 0 <= d < n and forest[c][d] > 0:
if c * n + d not in dist or dist[c * n + d] > step + 1:
dist[c * n + d] = step + 1
heappush(q, (dist[c * n + d] + f(c, d, x, y), c, d))
return -1
m, n = len(forest), len(forest[0])
trees = [
(forest[i][j], i, j) for i in range(m) for j in range(n) if forest[i][j] > 1
]
trees.sort()
i = j = 0
ans = 0
for _, x, y in trees:
t = bfs(i, j, x, y)
if t == -1:
return -1
ans += t
i, j = x, y
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O((R _C)^2) because BFS is performed for each of up to R_ C trees on an R _C grid. Space complexity is O(R_ C) for BFS queue and visited matrix. |
| 空间 | O(R*C) |
面试官常问的追问
外企场景- question_mark
Candidate uses BFS for shortest path between trees.
- question_mark
Candidate correctly handles blocked paths and returns -1 when unreachable.
- question_mark
Candidate sorts trees and uses priority queue to ensure correct cutting order.
常见陷阱
外企场景- error
Failing to cut trees strictly by increasing height.
- error
Not checking if a tree is unreachable, leading to wrong total steps.
- error
Inefficient BFS or repeated calculations for the same paths.
进阶变体
外企场景- arrow_right_alt
Forest with multiple trees of same height requiring tie-breaking by position.
- arrow_right_alt
Allow diagonal movement between cells for cutting trees.
- arrow_right_alt
Large sparse forest where BFS optimization with pruning is necessary.