Check if there is a valid path in a grid

Array Depth-First Search Breadth-First Search Union-Find Matrix

50.1% acceptance

Feb 25, 2026

881

326

You are given an m x n grid. Each cell of grid represents a street. The street of grid[i][j] can be: 1 which means a street connecting the left cell and the right cell. 2 which means a street connecting the upper cell and the lower cell. 3 which means a street connecting the left cell and the lower cell. 4 which means a street connecting the right cell and the lower cell. 5 which means a street connecting the left cell and the upper cell. 6 which means a street connecting the right cell and the upper cell. You will initially start at the street of the upper-left cell (0, 0). A valid path in the grid is a path that starts from the upper left cell (0, 0) and ends at the bottom-right cell (m - 1, n - 1). The path should only follow the streets. Notice that you are not allowed to change any street. Return true if there is a valid path in the grid or false otherwise.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn has_valid_path(grid: Vec<Vec<i32>>) -> bool {
    // For each street type, the directions it CONNECTS (not exits to):
    // 1: left(0), right(1)
    // 2: up(2), down(3)
    // 3: left(0), down(3)
    // 4: right(1), down(3)
    // 5: left(0), up(2)
    // 6: right(1), up(2)
    // Direction: 0=left, 1=right, 2=up, 3=down
    // Offsets: left=(-0,1?), no: 0=left→col-1, 1=right→col+1, 2=up→row-1, 3=down→row+1
    let connects: [[bool; 4]; 7] = [
      [false; 4],        // 0 (unused)
      [true, true, false, false],  // 1: left, right
      [false, false, true, true],  // 2: up, down
      [true, false, false, true],  // 3: left, down
      [false, true, false, true],  // 4: right, down
      [true, false, true, false],  // 5: left, up
      [false, true, true, false],  // 6: right, up
    ];
    let dr = [0i32, 0, -1, 1];
    let dc = [-1i32, 1, 0, 0];
    let opposite = [1usize, 0, 3, 2]; // opposite direction indices
    let m = grid.len();
    let n = grid[0].len();
    let mut visited = vec![vec![false; n]; m];
    let mut queue = std::collections::VecDeque::new();
    queue.push_back((0usize, 0usize));
    visited[0][0] = true;
    while let Some((r, c)) = queue.pop_front() {
      if r == m - 1 && c == n - 1 { return true; }
      let cell = grid[r][c] as usize;
      for dir in 0..4 {
        if !connects[cell][dir] { continue; }
        let nr = r as i32 + dr[dir];
        let nc = c as i32 + dc[dir];
        if nr < 0 || nr >= m as i32 || nc < 0 || nc >= n as i32 { continue; }
        let (nr, nc) = (nr as usize, nc as usize);
        if visited[nr][nc] { continue; }
        let next_cell = grid[nr][nc] as usize;
        if connects[next_cell][opposite[dir]] {
          visited[nr][nc] = true;
          queue.push_back((nr, nc));
        }
      }
    }
    false
  }
}