LeetCode 675. 为高尔夫比赛砍树

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

• 0 表示障碍，无法通过
• 1 表示空地，可以通过
• 比 1 大的数表示树，可以通过（树也需要砍掉）

你需要按照树的高度从小到大砍掉所有的树（即矩阵中所有大于 1 的值）。砍树时：

1. 你站在当前位置，砍掉一棵树后，可以走到该树的位置。
2. 你只能沿着上、下、左、右四个方向移动。
3. 你需要从起点 (0, 0) 开始，返回砍完所有树的最小步数。如果无法砍完所有树，返回 -1。

示例
输入：

[  
 [1,2,3],  
 [0,0,4],  
 [7,6,5]  
]  

输出：6
解释：按树高顺序砍树（2→3→4→5→6→7），路径需要最小步数 6。

解题过程

步骤 1：理解核心问题

• 砍树顺序由树的高度决定（从小到大），因此需先收集所有树的位置和高度，并按高度排序。
• 问题转化为：从起点开始，按顺序计算到下一棵树的最短路径步数，并累加。
• 若在某一阶段无法到达下一棵树，则直接返回 -1。

步骤 2：数据预处理

1. 遍历矩阵，收集所有树的位置 (r, c) 和高度 height，存入列表 trees。
2. 对 trees 按高度排序。
3. 起点为 (0,0)，但若 (0,0) 是障碍（值为 0）则直接返回 -1（因为无法出发）。

步骤 3：设计最短路径计算函数

• 由于需要多次计算两点的最短路径，使用 BFS（广度优先搜索）最合适。
• 函数 bfs(start, end) 返回从 start 到 end 的最短步数，若不可达返回 -1。
• BFS 实现时需注意：
  • 避开障碍（值为 0 的格子）。
  • 访问标记数组避免重复访问。

步骤 4：整体流程

1. 初始化当前位置 cur 为 (0,0)，总步数 total_steps = 0。
2. 按树高顺序遍历每棵树：
   • 用 BFS 计算从 cur 到当前树的最短路径步数 steps。
   • 若 steps == -1，返回 -1。
   • 否则累加 total_steps += steps，并更新 cur 为当前树的位置。
3. 返回 total_steps。

步骤 5：示例推导
示例矩阵：

[1,2,3]  
[0,0,4]  
[7,6,5]  

• 树高顺序：2(0,1) → 3(0,2) → 4(1,2) → 5(2,2) → 6(2,1) → 7(2,0)
• 计算路径：
  • (0,0)→(0,1)：步数 1
  • (0,1)→(0,2)：步数 1
  • (0,2)→(1,2)：步数 1（注意绕开障碍）
  • (1,2)→(2,2)：步数 1
  • (2,2)→(2,1)：步数 1
  • (2,1)→(2,0)：步数 1
• 总步数 = 6。

关键点

• 必须按树高顺序砍树，因此排序是关键。
• 每次移动是四方向 BFS，保证最短路径。
• 若任何两棵树之间不可达，整体失败。

通过以上步骤，即可高效解决该问题。