LeetCode算法日记-Day-45-为高尔夫比赛砍树矩阵

JAY.LIN 收录于算法日记系统化解题与思维记录 Leetcode

2025-09-18 约 3323 字预计阅读 7 分钟

https://bing.ee123.net/img/rand?artid=151753275

LeetCode算法日记 - Day 45: 为高尔夫比赛砍树、矩阵

1. 为高尔夫比赛砍树

你被请来给一个要举办高尔夫比赛的树林砍树。树林由一个 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.1 题目解析

题目本质

把可行走网格看作无权图，从起点(0,0)出发，按树高从低到高依次到达每一棵树。
每段“从当前点到下一棵树”的最短步数用一次 BFS 求两点最短路，最后把这些最短路长度相加。
任意一段不可达则返回 -1。

常规解法

直觉：把所有格子值拍平排序，然后对每个目标值在整张图做 BFS 去找同值格子。

问题分析

直觉做法会在每个目标值上对大量起点反复 BFS，复杂度接近 O(K × m × n × BFS)；
同时若用“值相等”判断目标坐标，容易写错索引或被重复值干扰（虽本题树高唯一，但坐标判断更稳）。
因此需要把问题拆成“多个两点最短路”。

思路转折

正确路线：
- 先收集所有树的三元组(height,i,j)，按 height 升序排序。
- 维护当前坐标(curI,curJ)，依次对下一棵树目标坐标(ti,tj)做一次 BFS 求两点最短路；若某次 BFS 返回 -1，则整体 -1；否则累加步数并把当前坐标更新到(ti,tj)。
- 这样每棵树只做一次 BFS，复杂度降为 O(K × m × n)，可通过。

1.2 解法

算法思想

将“按高度顺序砍树”的全局过程拆为 K 段“从当前点到下一棵树坐标”的两点最短路，每段用 BFS 分层搜索得到最短步数。坐标判断命中目标更安全：到达(ti,tj)即返回当前层数。

i）收集与排序

遍历 forest，找出所有 h>1 的格子，记录为 {h,i,j}。
对这些三元组按 h 升序排序。

ii）逐树前进

设当前坐标(si,sj) 初始为(0,0)。
依次取下一棵树目标(ti,tj)，调用 BFS 计算从(si,sj) 到(ti,tj) 的最短路。
若 BFS 返回 -1，则直接返回 -1；否则将步数累加到答案，并更新(si,sj) = (ti,tj)。

iii）BFS 细节

典型四方向分层搜索。
起点等于终点时直接返回 0。
合法入队条件可合写：边界内、未访问、非障碍。
命中条件用坐标判断：nx==ti 且 ny==tj 立即返回当前层步数+1。

易错点

目标命中勿写成 forest.get(0).get(b)==cur，应使用坐标命中(nx==ti && ny==tj)。
visited 不能复用，每次 BFS 都要新建 vis。
起点就是目标时要返回 0，避免多走一层。
如果使用合并判断条件写法，注意顺序与短路：边界检查应放在最前，否则会数组越界。

1.3 代码实现

import java.util.*;

class Solution {
    // 定义方向数组：上下左右四个方向
    int[] dx = {0,0,-1,1};
    int[] dy = {1,-1,0,0}; 
    int m,n;

    public int cutOffTree(List<List<Integer>> forest) {
        m = forest.size();
        n = forest.get(0).size();
        int result = 0;
        int si = 0, sj = 0;
        
        // 获取树：收集所有高度>1的单元格
        // 新数组列表与原数字建立映射
        List<int[]> listNum = new ArrayList<>();
        for(int i = 0; i < m ; i++){
            for(int j = 0; j < n ; j++){
                int h = forest.get(i).get(j);
                if(h > 1) listNum.add(new int[]{h,i,j});
            }
        }

        // 树排序：按高度升序
        listNum.sort(Comparator.comparingInt(a -> a[0]));

        // 进行遍历
        // si, sj 表示当前要进行 bfs 的格子坐标
        // ti, tj 表示要搜索的目标树坐标
        for(int[] t : listNum){
            int ti = t[1], tj = t[2];
            // 因为要从 forest 拿值, 所以方法需要传入 forest
            int tmp = bfs(forest, si, sj, ti, tj);
            // 因为0是有效值, 所以判断的时候使用-1来标记违法值
            if(tmp == -1) return -1;
            result += tmp;
            // 赋值到刚查到的最小树, 才能实现最少步骤完成任务
            si = ti;
            sj = tj;
        }
        return result;
    }

    // BFS 求两点最短路
    public int bfs(List<List<Integer>> forest, int si, int sj, int ti, int tj){
        // 如果起点和终点相同, 不用走
        if(si == ti && sj == tj) return 0;
        
        // 用于标记每一次遍历的监察数据, 涉及到多次调用不能污染 vis
        boolean[][] vis = new boolean[m][n];
        // 用于存储当前 si, sj 所代表的要进行 bfs 遍历的格子
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{si,sj});
        vis[si][sj] = true;

        int step = 0;

        while(!q.isEmpty()){
            int size = q.size();
            // 按层进行划分
            for(int i = 0; i < size; i++){
                int[] num = q.poll();
                int a = num[0], b = num[1];
                // 如果到达目标坐标, 返回当前步数
                if(a == ti && b == tj) return step;
                for(int j = 0 ; j < 4 ; j++){
                    int x = a + dx[j], y = b + dy[j];
                    // 边界内 + 非障碍 + 未访问 才能入队
                    if(x>=0 && x<m && y>=0 && y<n && forest.get(x).get(y) != 0 && !vis[x][y]){
                        q.offer(new int[]{x,y});
                        vis[x][y] = true;
                    }
                }
            }
            step++;
        }
        // 无法到达目标
        return -1;
    }
}

复杂度分析

**时间：**排序 O(K log K)；每棵树一次 BFS，最坏 O(mn)，合计 O(K × m × n)（K 为树数，K ≤ m×n）。
**空间：**visited 与队列最坏 O(mn)。

2. 矩阵

给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。

两个相邻元素间的距离为 1 。