Approach: Sort by Height + BFS Between Consecutive Trees
The rules fix the order: trees must be cut shortest to tallest. So the walk splits 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 = BFS. If any leg is unreachable (a tree walled off by
"0"s), return
“-1”.
use std::collections::VecDeque;
impl Solution {
pub fn cut_off_tree(forest: Vec<Vec>) -> i32 {
if forest.is_empty() || forest[0].is_empty() {
return -1;
}
let (m, n) = (forest.len(), forest[0].len());
// Height > 1 is a tree; height 1 is plain walkable ground. let mut trees: Vec<(i32, usize, usize)> = Vec::new(); for r in 0..m { for c in 0..n { if forest[r][c] > 1 { trees.push((forest[r][c], r, c)); } } } trees.sort_unstable_by_key(|&(h, _, _)| h); let mut total = 0; let (mut row, mut col) = (0usize, 0usize); for (_, tr, tc) in trees { let d = bfs(&forest, row, col, tr, tc); if d == -1 { return -1; // next tree is unreachable } total += d; row = tr; col = tc; } total }}
/// Shortest step count from (sr,sc) to (tr,tc); -1 if unreachable.
fn bfs(forest: &[Vec], sr: usize, sc: usize, tr: usize, tc: usize) -> i32 {
if sr == tr && sc == tc {
return 0;
}
let (m, n) = (forest.len(), forest[0].len());
let mut seen = vec![vec![false; n]; m];
let mut q: VecDeque<(usize, usize, i32)> = VecDeque::new();
seen[sr][sc] = true; q.push_back((sr, sc, 0)); while let Some((r, c, d)) = q.pop_front() { // i32 offsets avoid usize underflow at row/col 0 for (dr, dc) in [(1i32, 0i32), (-1, 0), (0, 1), (0, -1)] { let nr = r as i32 + dr; let nc = c as i32 + dc; if nr < 0 || nr >= m as i32 || nc < 0 || nc >= n as i32 { continue; } let (nr, nc) = (nr as usize, nc as usize); if seen[nr][nc] || forest[nr][nc] == 0 { continue; // visited, or blocked ground } if nr == tr && nc == tc { return d + 1; // early exit on hit } seen[nr][nc] = true; // mark on enqueue q.push_back((nr, nc, d + 1)); } } -1}
Key details
- Height
“1” is walkable ground, not a tree — only
“> 1” enters
“trees”. This is the classic bug in this problem.
“forest[nr][nc] == 0” is the only blocked case; you may freely walk over uncut trees.
“i32” offsets (
“r as i32 + dr”) instead of
“r - 1”, which would panic on underflow at index 0 in debug builds.
“seen” marked on enqueue, not dequeue, or a cell gets pushed multiple times.
- Distance rides in the queue tuple — no
“dist[][]” grid allocated per leg.
“bfs” is a free function taking
“&[Vec]”, since a closure capturing
“forest” while it’s also borrowed inside the loop is needlessly awkward.
“sort_unstable_by_key” is fine here: 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) for the sort.
- Space: O(m · n) for
“seen” and the queue, rebuilt per leg.
The logic matches the Python version I ran 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”.
