Unique paths iii

Array Backtracking Bit Manipulation Matrix

82.8% acceptance

Feb 25, 2026

5474

198

You are given an m x n integer array grid where grid[i][j] could be: 1 representing the starting square. There is exactly one starting square. 2 representing the ending square. There is exactly one ending square. 0 representing empty squares we can walk over. -1 representing obstacles that we cannot walk over. Return the number of 4-directional walks from the starting square to the ending square, that walk over every non-obstacle square exactly once.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn unique_paths_iii(mut grid: Vec<Vec<i32>>) -> i32 {
    let (m, n) = (grid.len(), grid[0].len());
    let mut start = (0, 0);
    let mut empty = 0;
    for i in 0..m { for j in 0..n {
      match grid[i][j] { 1 => { start = (i,j); empty += 1; } 0 => empty += 1, _ => {} }
    }}
    fn dfs(grid: &mut Vec<Vec<i32>>, i: usize, j: usize, remaining: i32) -> i32 {
      if grid[i][j] == 2 { return if remaining == 0 { 1 } else { 0 }; }
      let orig = grid[i][j];
      grid[i][j] = -1;
      let (m, n) = (grid.len(), grid[0].len());
      let mut res = 0;
      for (di, dj) in [(!0usize,0usize),(1,0),(0,!0usize),(0,1)] {
        let (ni, nj) = (i.wrapping_add(di), j.wrapping_add(dj));
        if ni < m && nj < n && grid[ni][nj] != -1 {
          let next_rem = if grid[ni][nj] == 2 { remaining } else { remaining - 1 };
          res += dfs(grid, ni, nj, next_rem);
        }
      }
      grid[i][j] = orig;
      res
    }
    dfs(&mut grid, start.0, start.1, empty - 1)
  }
}