LeetCode 675. 为高尔夫比赛砍树

字数 2236 2025-11-05 08:30:58

LeetCode 675. 为高尔夫比赛砍树

题目描述

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

0 表示障碍，无法通过。
1 表示平坦的草地，可以通过。
比 1 大的整数表示树，可以通过。这个整数值表示树的高度。

你需要按照从低到高的顺序砍掉所有的树。你需要找到从起点 (0, 0) 开始，砍完所有树所需行走的最短步数。如果你无法砍掉所有的树，则返回 -1。

在一步中，你可以向上、下、左、右四个方向之一移动一个单位。

解题过程循序渐进讲解

这个问题可以分解为两个核心部分：

确定砍树顺序：由于规则是必须从最矮的树开始砍，所以我们首先需要收集所有树的位置和高度，并按高度进行升序排序。
计算顺序点之间的最短路径：从起点 (0, 0) 开始，我们需要依次到达排序后的第一棵树、第二棵树...直到最后一棵树的位置。每一步移动，都需要计算从当前位置（起点或上一棵被砍的树）到下一棵树的最短路径步数。

因此，整个问题的解就是所有这些最短路径步数的总和。

步骤 1：识别问题核心 - 最短路径的序列求和

我们不能简单地一次性规划一条访问所有树的路径，因为砍伐顺序是强制的（由树高决定）。所以，正确的思路是：

将问题转化为一系列的最短路径子问题。
子问题：从点 A 到点 B，避开障碍物 (0)，所需的最少步数是多少？

步骤 2：选择解决最短路径子问题的算法

在一个网格图中，寻找两点之间的最短路径，且每一步的代价相同（都是1），最经典的算法是广度优先搜索（BFS）。BFS 能够保证我们第一次到达目标点时，所用的步数就是最短步数。

步骤 3：设计 BFS 函数

我们需要一个辅助函数 bfs(start, end)，它返回从 start 坐标到 end 坐标的最短步数。如果不可达，则返回一个特殊值（例如 -1）。

BFS 的标准步骤：

初始化：创建一个队列（通常先入先出），用于存储待访问的节点。同时，创建一个与树林矩阵同大小的 visited 矩阵（或集合），用于记录哪些位置已经被访问过，避免重复访问和死循环。
起点入队：将起点坐标 start 和当前的步数（初始为 0）加入队列，并标记起点为已访问。
循环处理队列：当队列不为空时：
a. 出队：从队列中取出一个节点（即一个坐标）以及到达该节点的步数。
b. 检查目标：如果这个节点就是目标终点 end，那么当前步数就是答案，直接返回。
c. 探索邻居：如果还不是终点，就检查这个节点的上、下、左、右四个邻居。
* 检查邻居坐标是否在矩阵范围内。
* 检查邻居位置不是障碍物 (grid[neighbor] != 0)。
* 检查邻居位置未被访问过。
d. 标记和入队：对于满足条件的邻居，将其标记为已访问，并将其坐标以及 当前步数 + 1 加入队列。
队列清空仍未找到目标：如果 BFS 循环结束（队列为空）都没有找到终点，说明从 start 到 end 不可达，返回 -1。

步骤 4：整合主算法

有了 BFS 函数后，主算法的逻辑就清晰了：

预处理：收集并排序树木：
- 遍历整个 m x n 的矩阵 grid。
- 如果某个位置的值大于 1，说明这是一棵树。我们将 (树的高度, 树的横坐标, 树的纵坐标) 作为一个元组，加入一个列表 trees 中。
- 对列表 trees 按照树的高度进行升序排序。这样，列表中的树就是我们需要依次砍伐的顺序。
初始化：
- 设总步数 total_steps = 0。
- 设当前位置 current_pos 为起点 (0, 0)。
依次处理每一棵树：
- 按顺序从排序好的 trees 列表中取出下一棵需要砍的树的坐标，作为目标 next_tree_pos。
- 调用 bfs(current_pos, next_tree_pos)，计算从 current_pos 走到 next_tree_pos 的最短步数 steps。
- 如果 steps == -1，说明这棵树无法到达，根据题意，整个任务失败，直接返回 -1。
- 否则，将 steps 累加到总步数 total_steps 上。
- 将当前位置 current_pos 更新为这棵刚被砍掉的树的位置 next_tree_pos，因为我们将从这里出发去砍下一棵更高的树。
返回结果：
- 当所有树都被成功处理完后，返回累加的总步数 total_steps。

步骤 5：复杂度分析

时间复杂度：最坏情况下，我们需要砍 T 棵树（T 是树的数量）。对于每一对连续的砍伐点（包括从起点到第一棵树），我们都需要执行一次 BFS。每次 BFS 的时间复杂度是 O(m * n)，因为最坏需要遍历整个网格。因此，总时间复杂度为 O(T * m * n)。
空间复杂度：主要是 BFS 中队列和已访问集合的开销，为 O(m * n)。

总结

解决 "为高尔夫比赛砍树" 的关键在于将强制顺序的路径问题，分解为多个经典的最短路径问题（BFS）。通过先排序确定任务序列，再逐个计算点对之间的最短距离并累加，最终得到答案。这个思路清晰地将一个复杂问题转化为了我们已经熟练掌握的基础算法组合。

LeetCode 675. 为高尔夫比赛砍树题目描述你被请来给一个要举办高尔夫比赛的树林砍树。树林由一个 m x n 的矩阵表示，其中： 0 表示障碍，无法通过。 1 表示平坦的草地，可以通过。比 1 大的整数表示树，可以通过。这个整数值表示树的高度。你需要按照从低到高的顺序砍掉所有的树。你需要找到从起点 (0, 0) 开始，砍完所有树所需行走的最短步数。如果你无法砍掉所有的树，则返回 -1 。在一步中，你可以向上、下、左、右四个方向之一移动一个单位。解题过程循序渐进讲解这个问题可以分解为两个核心部分：确定砍树顺序：由于规则是必须从最矮的树开始砍，所以我们首先需要收集所有树的位置和高度，并按高度进行升序排序。计算顺序点之间的最短路径：从起点 (0, 0) 开始，我们需要依次到达排序后的第一棵树、第二棵树...直到最后一棵树的位置。每一步移动，都需要计算从当前位置（起点或上一棵被砍的树）到下一棵树的最短路径步数。因此，整个问题的解就是所有这些最短路径步数的总和。步骤 1：识别问题核心 - 最短路径的序列求和我们不能简单地一次性规划一条访问所有树的路径，因为砍伐顺序是强制的（由树高决定）。所以，正确的思路是：将问题转化为一系列的最短路径子问题。子问题：从点 A 到点 B，避开障碍物 ( 0 )，所需的最少步数是多少？步骤 2：选择解决最短路径子问题的算法在一个网格图中，寻找两点之间的最短路径，且每一步的代价相同（都是1），最经典的算法是广度优先搜索（BFS）。BFS 能够保证我们第一次到达目标点时，所用的步数就是最短步数。步骤 3：设计 BFS 函数我们需要一个辅助函数 bfs(start, end) ，它返回从 start 坐标到 end 坐标的最短步数。如果不可达，则返回一个特殊值（例如 -1 ）。 BFS 的标准步骤：初始化：创建一个队列（通常先入先出），用于存储待访问的节点。同时，创建一个与树林矩阵同大小的 visited 矩阵（或集合），用于记录哪些位置已经被访问过，避免重复访问和死循环。起点入队：将起点坐标 start 和当前的步数（初始为 0）加入队列，并标记起点为已访问。循环处理队列：当队列不为空时： a. 出队：从队列中取出一个节点（即一个坐标）以及到达该节点的步数。 b. 检查目标：如果这个节点就是目标终点 end ，那么当前步数就是答案，直接返回。 c. 探索邻居：如果还不是终点，就检查这个节点的上、下、左、右四个邻居。 * 检查邻居坐标是否在矩阵范围内。 * 检查邻居位置不是障碍物 ( grid[neighbor] != 0 )。 * 检查邻居位置未被访问过。 d. 标记和入队：对于满足条件的邻居，将其标记为已访问，并将其坐标以及当前步数 + 1 加入队列。队列清空仍未找到目标：如果 BFS 循环结束（队列为空）都没有找到终点，说明从 start 到 end 不可达，返回 -1 。步骤 4：整合主算法有了 BFS 函数后，主算法的逻辑就清晰了：预处理：收集并排序树木：遍历整个 m x n 的矩阵 grid 。如果某个位置的值大于 1，说明这是一棵树。我们将 (树的高度, 树的横坐标, 树的纵坐标) 作为一个元组，加入一个列表 trees 中。对列表 trees 按照树的高度进行升序排序。这样，列表中的树就是我们需要依次砍伐的顺序。初始化：设总步数 total_steps = 0 。设当前位置 current_pos 为起点 (0, 0) 。依次处理每一棵树：按顺序从排序好的 trees 列表中取出下一棵需要砍的树的坐标，作为目标 next_tree_pos 。调用 bfs(current_pos, next_tree_pos) ，计算从 current_pos 走到 next_tree_pos 的最短步数 steps 。如果 steps == -1 ，说明这棵树无法到达，根据题意，整个任务失败，直接返回 -1 。否则，将 steps 累加到总步数 total_steps 上。将当前位置 current_pos 更新为这棵刚被砍掉的树的位置 next_tree_pos ，因为我们将从这里出发去砍下一棵更高的树。返回结果：当所有树都被成功处理完后，返回累加的总步数 total_steps 。步骤 5：复杂度分析时间复杂度：最坏情况下，我们需要砍 T 棵树（ T 是树的数量）。对于每一对连续的砍伐点（包括从起点到第一棵树），我们都需要执行一次 BFS。每次 BFS 的时间复杂度是 O(m * n) ，因为最坏需要遍历整个网格。因此，总时间复杂度为 O(T * m * n) 。空间复杂度：主要是 BFS 中队列和已访问集合的开销，为 O(m * n) 。总结解决 "为高尔夫比赛砍树" 的关键在于将强制顺序的路径问题，分解为多个经典的最短路径问题（BFS）。通过先排序确定任务序列，再逐个计算点对之间的最短距离并累加，最终得到答案。这个思路清晰地将一个复杂问题转化为了我们已经熟练掌握的基础算法组合。