Approach: Sort by Height + BFS Between Consecutive Trees
The rules force a fixed order: trees must be cut shortest to tallest. So the walk decomposes into independent legs — go from your current cell to the next required tree by the shortest path, pay that distance, repeat. Shortest path on an unweighted grid with obstacles is BFS. If any leg is unreachable (a tree walled off by
"0"s), return
“-1”.
from collections import deque
from typing import List
class Solution:
def cutOffTree(self, forest: List[List[int]]) -> int:
if not forest or not forest[0]:
return -1
m, n = len(forest), len(forest[0])
def bfs(sr: int, sc: int, tr: int, tc: int) -> int: """Shortest step count from (sr,sc) to (tr,tc); -1 if unreachable.""" if sr == tr and sc == tc: return 0 seen = [[False] * n for _ in range(m)] seen[sr][sc] = True q = deque([(sr, sc, 0)]) # (row, col, dist) while q: r, c, d = q.popleft() for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)): if 0 <= nr < m and 0 <= nc < n and not seen[nr][nc] and forest[nr][nc] > 0: if nr == tr and nc == tc: return d + 1 # early exit on hit seen[nr][nc] = True # mark on enqueue q.append((nr, nc, d + 1)) return -1 # Height > 1 means a tree; cut in ascending height order. trees = sorted((forest[r][c], r, c) for r in range(m) for c in range(n) if forest[r][c] > 1) total = row = col = 0 for _, tr, tc in trees: d = bfs(row, col, tr, tc) if d == -1: return -1 total += d row, col = tr, tc return totalKey details
- Height
“1” is walkable ground, not a tree. Only
“> 1” enters the
“trees” list — the classic bug here is treating
“1” as a tree.
“forest[nr][nc] > 0” is the walkability test:
“0” is blocked, everything else is passable (including trees you haven’t cut yet — you may walk over them).
- Mark
“seen” on enqueue, not dequeue, or the same cell gets pushed repeatedly. - Distance rides in the queue tuple, so no
“dist[][]” grid per leg. - Early return the moment the target is generated as a neighbor; no need to drain the queue.
- Sorting is by height only — heights are guaranteed distinct, so no tie-break needed.
Complexity
- Time: O(T · m · n) for T trees (one BFS per leg), plus O(T log T) to sort.
- Space: O(m · n) for
“seen” and the queue, rebuilt 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”.
