元宝 LeetCode 675. Cut Off Trees for Golf Event Rust Implement

Approach: Sort by Height BFS Between Consecutive TreesThe 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 by0s), return“-1”.use std::collections::VecDeque;impl Solution {pub fn cut_off_tree(forest: VecVec) - 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 detailsHeight“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.ComplexityTime: 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”.