Escape a large maze

Array Hash Table Depth-First Search Breadth-First Search

36.3% acceptance

Feb 25, 2026

712

173

There is a 1 million by 1 million grid on an XY-plane, and the coordinates of each grid square are (x, y). We start at the source = [sx, sy] square and want to reach the target = [tx, ty] square. There is also an array of blocked squares, where each blocked[i] = [xi, yi] represents a blocked square with coordinates (xi, yi). Each move, we can walk one square north, east, south, or west if the square is not in the array of blocked squares. We are also not allowed to walk outside of the grid. Return true if and only if it is possible to reach the target square from the source square through a sequence of valid moves.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn is_escape_possible(blocked: Vec<Vec<i32>>, source: Vec<i32>, target: Vec<i32>) -> bool {
    use std::collections::{HashSet, VecDeque};
    if blocked.is_empty() { return true; }
    let block_set: HashSet<(i32,i32)> = blocked.iter().map(|b| (b[0], b[1])).collect();
    let max_enclosed = blocked.len() * blocked.len() / 2;
    let bfs = |start: (i32,i32), end: (i32,i32)| -> bool {
      let mut visited = HashSet::new();
      let mut queue = VecDeque::new();
      queue.push_back(start);
      visited.insert(start);
      while let Some((r, c)) = queue.pop_front() {
        if (r, c) == end { return true; }
        if visited.len() > max_enclosed { return true; }
        for (dr, dc) in [(0i32,1i32),(0,-1),(1,0),(-1,0)] {
          let (nr, nc) = (r+dr, c+dc);
          if nr < 0 || nr >= 1_000_000 || nc < 0 || nc >= 1_000_000 { continue; }
          if block_set.contains(&(nr,nc)) { continue; }
          if visited.insert((nr,nc)) { queue.push_back((nr,nc)); }
        }
      }
      false
    };
    let s = (source[0], source[1]);
    let t = (target[0], target[1]);
    bfs(s, t) && bfs(t, s)
  }
}