Skip to content

3665. Twisted Mirror Path Count

SourceBiweekly Contest 164 Q3DifficultyMediumRating1883

Description

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.

Note: If a reflection moves the robot into a mirror cell, the robot is immediately reflected again based on the direction it used to enter that mirror: if it entered while moving right, it will be turned down; if it entered while moving down, it will be turned right. This process will continue until either the last cell is reached, the robot moves out of bounds or the robot moves to a non-mirror cell.

 

Example 1:

Input: grid = [[0,1,0],[0,0,1],[1,0,0]]

Output: 5

Explanation:

Number Full Path
1 (0, 0) → (0, 1) [M] → (1, 1) → (1, 2) [M] → (2, 2)
2 (0, 0) → (0, 1) [M] → (1, 1) → (2, 1) → (2, 2)
3 (0, 0) → (1, 0) → (1, 1) → (1, 2) [M] → (2, 2)
4 (0, 0) → (1, 0) → (1, 1) → (2, 1) → (2, 2)
5 (0, 0) → (1, 0) → (2, 0) [M] → (2, 1) → (2, 2)

  • [M] indicates the robot attempted to enter a mirror cell and instead reflected.

Example 2:

Input: grid = [[0,0],[0,0]]

Output: 2

Explanation:

Number Full Path
1 (0, 0) → (0, 1) → (1, 1)
2 (0, 0) → (1, 0) → (1, 1)

Example 3:

Input: grid = [[0,1,1],[1,1,0]]

Output: 1

Explanation:

Number Full Path
1 (0, 0) → (0, 1) [M] → (1, 1) [M] → (1, 2)
(0, 0) → (1, 0) [M] → (1, 1) [M] → (2, 1) goes out of bounds, so it is invalid.

 

Constraints:

  • m == grid.length
  • n == grid[i].length
  • 2 <= m, n <= 500
  • grid[i][j] is either 0 or 1.
  • grid[0][0] == grid[m - 1][n - 1] == 0

Solutions

Solution 1: Dynamic Programming

Thinking

Without mirrors, paths from the top-left to the bottom-right that only step right or down can be counted cell by cell. Sides reach \(500\), so listing every path grows exponentially and does not fit.

A mirror bends the direction. Entering to the right turns the robot downward, entering downward turns it right, a chain of mirrors bends again at once, and a step that leaves the board is not counted. An arrival count alone no longer says which way the next step must go.

The robot never moves left or up, so the cells have no cycles. Each cell only needs the number of ways that leave it to the right and the number that leave it downward. On an empty cell both equal the sum of the left and upper inflows; on a mirror the two inflows are swapped.

Fill an \(m \times n\) table from left to right, row by row. The rightward component of the left neighbor and the downward component of the cell above are already known. The origin has no predecessor, so it is seeded with \(1\) way. The destination is an empty cell, and either component there is the answer.

We define \(f[i][j][0]\) as the number of ways to leave cell \((i, j)\) to the right, and \(f[i][j][1]\) as the number of ways to leave downward. Every value is taken modulo \(10^9+7\).

Let \(r\) be the number of ways to enter \((i, j)\) from the left, and \(d\) the number of ways to enter from above. If \(j > 0\), then \(r = f[i][j - 1][0]\); otherwise \(r = 0\). If \(i > 0\), then \(d = f[i - 1][j][1]\). The origin has no predecessor, so set \(d = 1\) there. Every other cell in the first row has no cell above, so \(d = 0\).

On an empty cell, every path that arrives may continue either right or down, so both outgoing counts equal \(r + d\):

\[ f[i][j][0] = f[i][j][1] = (r + d) \bmod (10^9+7). \]

On a mirror, a path that enters from above is reflected to the right, and a path that enters from the left is reflected downward. The path does not stop on the mirror:

\[ f[i][j][0] = d, \quad f[i][j][1] = r. \]

A reflection that crosses the border has no successor and is dropped. The problem guarantees \(\textit{grid}[0][0] = \textit{grid}[m - 1][n - 1] = 0\), so both components at the destination equal the number of ways to arrive. Return \(f[m - 1][n - 1][0]\).

Compute cells in increasing row order, and from left to right inside a row. Each cell depends only on the left neighbor and the cell above, both of which are already filled.

The time complexity is \(O(mn)\) and the space complexity is \(O(mn)\), where \(m\) and \(n\) are the number of rows and columns.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def uniquePaths(self, grid: List[List[int]]) -> int:
        mod = 10**9 + 7
        m, n = len(grid), len(grid[0])
        f = [[[0, 0] for _ in range(n)] for _ in range(m)]
        for i, row in enumerate(grid):
            for j, x in enumerate(row):
                r = f[i][j - 1][0] if j else 0
                d = f[i - 1][j][1] if i else 0
                if i == 0 and j == 0:
                    d = 1
                if x == 1:
                    f[i][j] = [d, r]
                else:
                    s = (r + d) % mod
                    f[i][j] = [s, s]
        return f[-1][-1][0]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int uniquePaths(int[][] grid) {
        final int mod = (int) 1e9 + 7;
        int m = grid.length, n = grid[0].length;
        int[][][] f = new int[m][n][2];
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                int r = j > 0 ? f[i][j - 1][0] : 0;
                int d = i > 0 ? f[i - 1][j][1] : 0;
                if (i == 0 && j == 0) {
                    d = 1;
                }
                if (grid[i][j] == 1) {
                    f[i][j][0] = d;
                    f[i][j][1] = r;
                } else {
                    int s = (r + d) % mod;
                    f[i][j][0] = f[i][j][1] = s;
                }
            }
        }
        return f[m - 1][n - 1][0];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int uniquePaths(vector<vector<int>>& grid) {
        const int mod = 1e9 + 7;
        int m = grid.size(), n = grid[0].size();
        vector<vector<array<int, 2>>> f(m, vector<array<int, 2>>(n));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                int r = j > 0 ? f[i][j - 1][0] : 0;
                int d = i > 0 ? f[i - 1][j][1] : 0;
                if (i == 0 && j == 0) {
                    d = 1;
                }
                if (grid[i][j] == 1) {
                    f[i][j] = {d, r};
                } else {
                    int s = (r + d) % mod;
                    f[i][j] = {s, s};
                }
            }
        }
        return f[m - 1][n - 1][0];
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
func uniquePaths(grid [][]int) int {
    const mod = int(1e9 + 7)
    m, n := len(grid), len(grid[0])
    f := make([][][2]int, m)
    for i := range f {
        f[i] = make([][2]int, n)
    }
    for i, row := range grid {
        for j, x := range row {
            r, d := 0, 0
            if j > 0 {
                r = f[i][j-1][0]
            }
            if i > 0 {
                d = f[i-1][j][1]
            }
            if i == 0 && j == 0 {
                d = 1
            }
            if x == 1 {
                f[i][j] = [2]int{d, r}
            } else {
                s := (r + d) % mod
                f[i][j] = [2]int{s, s}
            }
        }
    }
    return f[m-1][n-1][0]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function uniquePaths(grid: number[][]): number {
    const mod = 1e9 + 7;
    const m = grid.length;
    const n = grid[0].length;
    const f: number[][][] = Array.from({ length: m }, () =>
        Array.from({ length: n }, () => [0, 0]),
    );
    for (let i = 0; i < m; ++i) {
        for (let j = 0; j < n; ++j) {
            let r = j > 0 ? f[i][j - 1][0] : 0;
            let d = i > 0 ? f[i - 1][j][1] : 0;
            if (i === 0 && j === 0) {
                d = 1;
            }
            if (grid[i][j] === 1) {
                f[i][j] = [d, r];
            } else {
                const s = (r + d) % mod;
                f[i][j] = [s, s];
            }
        }
    }
    return f[m - 1][n - 1][0];
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
impl Solution {
    pub fn unique_paths(grid: Vec<Vec<i32>>) -> i32 {
        const MOD: i32 = 1_000_000_007;
        let m = grid.len();
        let n = grid[0].len();
        let mut f = vec![vec![(0i32, 0i32); n]; m];
        for i in 0..m {
            for j in 0..n {
                let r = if j > 0 { f[i][j - 1].0 } else { 0 };
                let mut d = if i > 0 { f[i - 1][j].1 } else { 0 };
                if i == 0 && j == 0 {
                    d = 1;
                }
                f[i][j] = if grid[i][j] == 1 {
                    (d, r)
                } else {
                    let s = (r + d) % MOD;
                    (s, s)
                };
            }
        }
        f[m - 1][n - 1].0
    }
}

Solution 2: Dynamic Programming (Space Optimization)

Thinking

In Solution 1, \(f[i][j]\) reads only the rightward flow of the cell to its left on the same row, and the downward flow of the cell above in the same column. Once a row is finished, earlier rows are never read again.

A rolling array of length \(n + 1\) keeps one pair per column. While column \(j\) is updated, the left neighbor already holds this row's rightward flow and this column still holds the previous row's downward flow. Overwriting in place brings the space from \(O(mn)\) down to \(O(n)\).

In Solution 1, cell \(f[i][j]\) depends only on the rightward flow of the left neighbor and the downward flow of the cell above, so finished rows can be discarded.

Let \(f\) be an array of length \(n + 1\) that stores the latest pair for each column. \(f[j + 1][0]\) and \(f[j + 1][1]\) are the rightward and downward ways leaving column \(j\). The extra slot \(f[0]\) is the left border, and both of its components stay \(0\).

Scanning a row from left to right, read \(r = f[j][0]\) and \(d = f[j + 1][1]\) before updating column \(j\), then write the same transition as in Solution 1 back into \(f[j + 1]\). At that moment \(r\) is already the new value from the left cell of this row, while \(d\) is still the previous row's downward flow.

Initialize \(f[1] = (1, 1)\), so the origin reads an inflow of \(1\) from above. Return \(f[n][0]\).

The time complexity is \(O(mn)\) and the space complexity is \(O(n)\), where \(m\) and \(n\) are the number of rows and columns.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def uniquePaths(self, grid: List[List[int]]) -> int:
        mod = 10**9 + 7
        n = len(grid[0])
        f = [[0, 0] for _ in range(n + 1)]
        f[1] = [1, 1]
        for row in grid:
            for j, x in enumerate(row):
                r, d = f[j][0], f[j + 1][1]
                if x == 1:
                    f[j + 1] = [d, r]
                else:
                    s = (r + d) % mod
                    f[j + 1] = [s, s]
        return f[n][0]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int uniquePaths(int[][] grid) {
        final int mod = (int) 1e9 + 7;
        int n = grid[0].length;
        int[][] f = new int[n + 1][2];
        f[1][0] = f[1][1] = 1;
        for (int[] row : grid) {
            for (int j = 0; j < n; ++j) {
                int r = f[j][0], d = f[j + 1][1];
                if (row[j] == 1) {
                    f[j + 1][0] = d;
                    f[j + 1][1] = r;
                } else {
                    int s = (r + d) % mod;
                    f[j + 1][0] = f[j + 1][1] = s;
                }
            }
        }
        return f[n][0];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int uniquePaths(vector<vector<int>>& grid) {
        const int mod = 1e9 + 7;
        int n = grid[0].size();
        vector<array<int, 2>> f(n + 1);
        f[1] = {1, 1};
        for (auto& row : grid) {
            for (int j = 0; j < n; ++j) {
                int r = f[j][0], d = f[j + 1][1];
                if (row[j] == 1) {
                    f[j + 1] = {d, r};
                } else {
                    int s = (r + d) % mod;
                    f[j + 1] = {s, s};
                }
            }
        }
        return f[n][0];
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
func uniquePaths(grid [][]int) int {
    const mod = int(1e9 + 7)
    n := len(grid[0])
    f := make([][2]int, n+1)
    f[1] = [2]int{1, 1}
    for _, row := range grid {
        for j, x := range row {
            r, d := f[j][0], f[j+1][1]
            if x == 1 {
                f[j+1] = [2]int{d, r}
            } else {
                s := (r + d) % mod
                f[j+1] = [2]int{s, s}
            }
        }
    }
    return f[n][0]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
function uniquePaths(grid: number[][]): number {
    const mod = 1e9 + 7;
    const n = grid[0].length;
    const f: number[][] = Array.from({ length: n + 1 }, () => [0, 0]);
    f[1] = [1, 1];
    for (const row of grid) {
        for (let j = 0; j < n; ++j) {
            const r = f[j][0];
            const d = f[j + 1][1];
            if (row[j] === 1) {
                f[j + 1] = [d, r];
            } else {
                const s = (r + d) % mod;
                f[j + 1] = [s, s];
            }
        }
    }
    return f[n][0];
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
impl Solution {
    pub fn unique_paths(grid: Vec<Vec<i32>>) -> i32 {
        const MOD: i32 = 1_000_000_007;
        let n = grid[0].len();
        let mut f = vec![(0i32, 0i32); n + 1];
        f[1] = (1, 1);
        for row in &grid {
            for (j, &x) in row.iter().enumerate() {
                let (r, d) = (f[j].0, f[j + 1].1);
                f[j + 1] = if x == 1 {
                    (d, r)
                } else {
                    let s = (r + d) % MOD;
                    (s, s)
                };
            }
        }
        f[n].0
    }
}

Comments