Find a safe walk through a grid

Array Breadth-First Search Graph Theory Heap (Priority Queue) Matrix Shortest Path

32.7% acceptance

Feb 25, 2026

228

You are given an m x n binary matrix grid and an integer health. You start on the upper-left corner (0, 0) and would like to get to the lower-right corner (m-1, n-1). You can move up, down, left, or right from one cell to another adjacent cell as long as your health remains positive. Cells (i, j) with grid[i][j] = 1 are considered unsafe and reduce your health by 1. Return true if you can reach the final cell with a health value of 1 or more.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn find_safe_walk(grid: Vec<Vec<i32>>, health: i32) -> bool {
    let m = grid.len();
    let n = grid[0].len();
    // BFS/Dijkstra: min health consumed to reach each cell
    // Use dist = min unsafe cells encountered
    let mut dist = vec![vec![i32::MAX; n]; m];
    dist[0][0] = grid[0][0];
    let mut q = std::collections::VecDeque::new();
    q.push_back((0usize, 0usize));
    let dirs = [(0i32,1i32),(0,-1),(1,0),(-1,0)];
    while let Some((r, c)) = q.pop_front() {
      for (dr, dc) in dirs {
        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);
        let nd = dist[r][c] + grid[nr][nc];
        if nd < dist[nr][nc] {
          dist[nr][nc] = nd;
          q.push_back((nr, nc));
        }
      }
    }
    dist[m-1][n-1] < health
  }
}