Grid teleportation traversal

Array Hash Table Breadth-First Search Matrix

23.3% acceptance

Feb 25, 2026

135

You are given a 2D character grid matrix of size m x n, represented as an array of strings, where matrix[i][j] represents the cell at the intersection of the ith row and jth column. Each cell is one of the following: '.' representing an empty cell. '#' representing an obstacle. An uppercase letter ('A'-'Z') representing a teleportation portal. You start at the top-left cell (0, 0), and your goal is to reach the bottom-right cell (m - 1, n - 1). You can move from the current cell to any adjacent cell (up, down, left, right) as long as the destination cell is within the grid bounds and is not an obstacle. If you step on a cell containing a portal letter and you haven't used that portal letter before, you may instantly teleport to any other cell in the grid with the same letter. This teleportation does not count as a move, but each portal letter can be used at most once during your journey. Return the minimum number of moves required to reach the bottom-right cell. If it is not possible to reach the destination, return -1.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn min_moves(matrix: Vec<String>) -> i32 {
    use std::collections::VecDeque;
    let m = matrix.len();
    let n = matrix[0].len();
    let grid: Vec<Vec<u8>> = matrix.iter().map(|s| s.bytes().collect()).collect();

    // For each portal letter, collect its positions
    let mut portal_cells: Vec<Vec<(usize, usize)>> = vec![vec![]; 26];
    for r in 0..m {
      for c in 0..n {
        let ch = grid[r][c];
        if ch.is_ascii_uppercase() {
          portal_cells[(ch - b'A') as usize].push((r, c));
        }
      }
    }

    // 0-1 BFS: normal moves cost 1, portal teleportation costs 0.
    // KEY: trigger portals at POP time (finalized distance), not at SET time.
    // This prevents a portal from being consumed at a suboptimal distance,
    // which would block a cheaper path from using it later.
    let mut dist = vec![vec![i32::MAX; n]; m];
    let mut visited = vec![vec![false; n]; m];
    let mut portal_used = vec![false; 26];
    let mut deque: VecDeque<(usize, usize)> = VecDeque::new();

    dist[0][0] = 0;
    deque.push_back((0, 0));

    let dirs: [(i32, i32); 4] = [(-1, 0), (1, 0), (0, -1), (0, 1)];

    while let Some((r, c)) = deque.pop_front() {
      if visited[r][c] { continue; }
      visited[r][c] = true;
      let d = dist[r][c];
      if r == m - 1 && c == n - 1 { return d; }

      // Handle portal at the current cell (0-cost teleport to all same-letter cells)
      let ch = grid[r][c];
      if ch.is_ascii_uppercase() {
        let p = (ch - b'A') as usize;
        if !portal_used[p] {
          portal_used[p] = true;
          for &(pr, pc) in &portal_cells[p] {
            if !visited[pr][pc] && dist[pr][pc] > d {
              dist[pr][pc] = d;
              deque.push_front((pr, pc));
            }
          }
        }
      }

      // Normal moves (cost 1)
      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);
        if visited[nr][nc] || grid[nr][nc] == b'#' { continue; }
        if dist[nr][nc] > d + 1 {
          dist[nr][nc] = d + 1;
          deque.push_back((nr, nc));
        }
      }
    }

    if dist[m - 1][n - 1] == i32::MAX { -1 } else { dist[m - 1][n - 1] }
  }
}