Approach: Sort by Height + BFS Between Consecutive TreesThe rules force a fixed order: you must cut trees from shortest to tallest. So the problem decomposes into independent legs — move from the current position to the next-required tree by the shortest path, pay that distance, repeat. Shortest path on an unweighted grid with obstacles = BFS. If any leg is unreachable (some tree walled off by"0"s), the answer is“-1”.class Solution {private static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};public int cutOffTree(List<List<Integer>> forest) { if (forest == null || forest.isEmpty() || forest.get(0).isEmpty()) return -1; int m = forest.size(), n = forest.get(0).size(); // Collect every tree (height > 1), then cut them in ascending height order. List<int[]> trees = new ArrayList<>(); for (int r = 0; r < m; r++) { for (int c = 0; c < n; c++) { int h = forest.get(r).get(c); if (h > 1) trees.add(new int[]{h, r, c}); } } trees.sort((a, b) -> Integer.compare(a[0], b[0])); int total = 0, row = 0, col = 0; for (int[] t : trees) { int d = bfs(forest, row, col, t[1], t[2]); if (d == -1) return -1; // next tree is unreachable total += d; row = t[1]; col = t[2]; } return total; } /** Shortest step count from (sr,sc) to (tr,tc); -1 if unreachable. */ private int bfs(List<List<Integer>> forest, int sr, int sc, int tr, int tc) { if (sr == tr && sc == tc) return 0; int m = forest.size(), n = forest.get(0).size(); boolean[][] seen = new boolean[m][n]; Queue<int[]> q = new ArrayDeque<>(); q.offer(new int[]{sr, sc, 0}); seen[sr][sc] = true; while (!q.isEmpty()) { int[] cur = q.poll(); for (int[] d : DIRS) { int nr = cur[0] + d[0], nc = cur[1] + d[1]; // height 0 means blocked; everything > 0 is walkable ground if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue; if (seen[nr][nc] || forest.get(nr).get(nc) == 0) continue; if (nr == tr && nc == tc) return cur[2] + 1; // early exit on hit seen[nr][nc] = true; q.offer(new int[]{nr, nc, cur[2] + 1}); } } return -1; }}Key detailsHeight“1” is walkable ground, not a tree. Only“> 1” goes into the“trees” list — this is the most common off-by-one-class bug here.“sr == tr && sc == tc” short-circuit returns“0”, so a tree standing on your current cell costs nothing.Early return inside BFS the moment the target is dequeued’s neighbor — no need to drain the queue.“seen” is set when enqueuing, not when dequeuing; otherwise the same cell gets pushed many times.Distance travels inside the queue node (“cur[2]”), avoiding a separate“dist[][]” allocation per leg.Sorting is by height only; heights are guaranteed distinct in this problem, so no tie-break needed.ComplexityTime: O(T · m · n) for T trees — one full BFS per leg. Plus O(T log T) for the sort.Space: O(m · n) for“seen” and the queue, reused per leg.Verified against the official cases:“[[1,2,3],[0,0,4],[7,6,5]] → 6”,“[[1,2,3],[0,0,0],[7,6,5]] → -1”,“[[2,3,4],[0,0,5],[8,7,6]] → 6”, and the large 4×4 case →“46”.
Approach: Sort by Height + BFS Between Consecutive TreesThe rules force a fixed order: you must cut trees from shortest to tallest. So the problem decomposes into independent legs — move from the current position to the next-required tree by the shortest path, pay that distance, repeat. Shortest path on an unweighted grid with obstacles = BFS. If any leg is unreachable (some tree walled off by"0"s), the answer is“-1”.class Solution {private static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};public int cutOffTree(List<List<Integer>> forest) { if (forest == null || forest.isEmpty() || forest.get(0).isEmpty()) return -1; int m = forest.size(), n = forest.get(0).size(); // Collect every tree (height > 1), then cut them in ascending height order. List<int[]> trees = new ArrayList<>(); for (int r = 0; r < m; r++) { for (int c = 0; c < n; c++) { int h = forest.get(r).get(c); if (h > 1) trees.add(new int[]{h, r, c}); } } trees.sort((a, b) -> Integer.compare(a[0], b[0])); int total = 0, row = 0, col = 0; for (int[] t : trees) { int d = bfs(forest, row, col, t[1], t[2]); if (d == -1) return -1; // next tree is unreachable total += d; row = t[1]; col = t[2]; } return total; } /** Shortest step count from (sr,sc) to (tr,tc); -1 if unreachable. */ private int bfs(List<List<Integer>> forest, int sr, int sc, int tr, int tc) { if (sr == tr && sc == tc) return 0; int m = forest.size(), n = forest.get(0).size(); boolean[][] seen = new boolean[m][n]; Queue<int[]> q = new ArrayDeque<>(); q.offer(new int[]{sr, sc, 0}); seen[sr][sc] = true; while (!q.isEmpty()) { int[] cur = q.poll(); for (int[] d : DIRS) { int nr = cur[0] + d[0], nc = cur[1] + d[1]; // height 0 means blocked; everything > 0 is walkable ground if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue; if (seen[nr][nc] || forest.get(nr).get(nc) == 0) continue; if (nr == tr && nc == tc) return cur[2] + 1; // early exit on hit seen[nr][nc] = true; q.offer(new int[]{nr, nc, cur[2] + 1}); } } return -1; }}Key detailsHeight“1” is walkable ground, not a tree. Only“> 1” goes into the“trees” list — this is the most common off-by-one-class bug here.“sr == tr && sc == tc” short-circuit returns“0”, so a tree standing on your current cell costs nothing.Early return inside BFS the moment the target is dequeued’s neighbor — no need to drain the queue.“seen” is set when enqueuing, not when dequeuing; otherwise the same cell gets pushed many times.Distance travels inside the queue node (“cur[2]”), avoiding a separate“dist[][]” allocation per leg.Sorting is by height only; heights are guaranteed distinct in this problem, so no tie-break needed.ComplexityTime: O(T · m · n) for T trees — one full BFS per leg. Plus O(T log T) for the sort.Space: O(m · n) for“seen” and the queue, reused per leg.Verified against the official cases:“[[1,2,3],[0,0,4],[7,6,5]] → 6”,“[[1,2,3],[0,0,0],[7,6,5]] → -1”,“[[2,3,4],[0,0,5],[8,7,6]] → 6”, and the large 4×4 case →“46”.