Twisted mirror path count

Array Dynamic Programming Matrix

48.1% acceptance

Feb 25, 2026

Given an m x n binary grid grid where: grid[i][j] == 0 represents an empty cell, and grid[i][j] == 1 represents a mirror. A robot starts at the top-left corner of the grid (0, 0) and wants to reach the bottom-right corner (m - 1, n - 1). It can move only right or down. If the robot attempts to move into a mirror cell, it is reflected before entering that cell: If it tries to move right into a mirror, it is turned down and moved into the cell directly below the mirror. If it tries to move down into a mirror, it is turned right and moved into the cell directly to the right of the mirror. If this reflection would cause the robot to move outside the grid boundaries, the path is considered invalid and should not be counted. Return the number of unique valid paths from (0, 0) to (m - 1, n - 1). Since the answer may be very large, return it modulo 109 + 7.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn unique_paths(grid: Vec<Vec<i32>>) -> i32 {
    const MOD: i64 = 1_000_000_007;
    let m = grid.len();
    let n = grid[0].len();

    // move_robot: from (r,c) in direction d (0=right, 1=down), follow chain of reflections
    // returns final landing cell or None if hits boundary
    let move_robot = |mut r: usize, mut c: usize, mut d: usize| -> Option<(usize, usize)> {
      loop {
        let (nr, nc) = if d == 0 { (r, c + 1) } else { (r + 1, c) };
        if d == 0 && nc >= n { return None; }
        if d == 1 && nr >= m { return None; }
        if grid[nr][nc] == 0 {
          return Some((nr, nc));
        }
        // Mirror: reflect
        if d == 0 {
          // Moving right into mirror at (nr, nc): turn down
          r = nr; c = nc; d = 1;
        } else {
          // Moving down into mirror at (nr, nc): turn right
          r = nr; c = nc; d = 0;
        }
      }
    };

    let mut dp = vec![vec![0i64; n]; m];
    dp[0][0] = 1;
    // Process in order of increasing r+c (topological order)
    for diag in 0..(m + n - 1) {
      for r in 0..m {
        let c = if diag >= r { diag - r } else { continue };
        if c >= n { continue; }
        if grid[r][c] == 1 { continue; } // mirror cells not visited
        let val = dp[r][c];
        if val == 0 { continue; }
        // Move right
        if let Some((nr, nc)) = move_robot(r, c, 0) {
          dp[nr][nc] = (dp[nr][nc] + val) % MOD;
        }
        // Move down
        if let Some((nr, nc)) = move_robot(r, c, 1) {
          dp[nr][nc] = (dp[nr][nc] + val) % MOD;
        }
      }
    }
    dp[m - 1][n - 1] as i32
  }
}