Cut off trees for golf event

Array Breadth-First Search Heap (Priority Queue) Matrix

36.1% acceptance

Feb 20, 2026

1291

690

Cut off trees in order from shortest to tallest. Return minimum steps needed, or -1 if any tree is unreachable. Starting position is (0,0).

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

use std::collections::VecDeque;
impl Solution {
  pub fn cut_off_tree(forest: Vec<Vec<i32>>) -> i32 {
    let m = forest.len();
    let n = forest[0].len();
    // Collect trees sorted by height
    let mut trees: Vec<(i32, usize, usize)> = Vec::new();
    for i in 0..m {
      for j in 0..n {
        if forest[i][j] > 1 {
          trees.push((forest[i][j], i, j));
        }
      }
    }
    trees.sort_unstable();

    fn bfs(forest: &Vec<Vec<i32>>, sr: usize, sc: usize, tr: usize, tc: usize) -> i32 {
      let m = forest.len();
      let n = forest[0].len();
      if sr == tr && sc == tc { return 0; }
      let mut visited = vec![vec![false; n]; m];
      let mut queue = VecDeque::new();
      queue.push_back((sr, sc, 0i32));
      visited[sr][sc] = true;
      while let Some((r, c, steps)) = queue.pop_front() {
        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 {
            let nr = nr as usize;
            let nc = nc as usize;
            if !visited[nr][nc] && forest[nr][nc] != 0 {
              if nr == tr && nc == tc { return steps + 1; }
              visited[nr][nc] = true;
              queue.push_back((nr, nc, steps + 1));
            }
          }
        }
      }
      -1
    }

    let mut total = 0i32;
    let (mut cr, mut cc) = (0usize, 0usize);
    for (_, tr, tc) in &trees {
      let steps = bfs(&forest, cr, cc, *tr, *tc);
      if steps == -1 { return -1; }
      total += steps;
      cr = *tr;
      cc = *tc;
    }
    total
  }
}