3665. Twisted Mirror Path Count

1. Description

An m x n binary grid contains empty cells (0) and mirrors (1).
A robot travels from (0,0) to (m - 1,n - 1), choosing right or down moves at empty cells.
Trying to enter a mirror while moving right redirects the robot to the cell below the mirror. Trying to enter one while moving down redirects it to the cell to the mirror’s right.
If that cell is another mirror, continue reflecting according to the arrival direction. Discard any route that leaves the grid.
Return the number of distinct valid paths modulo 10$^9$ + 7.

2. Example

Example 1

Input: grid = [[0,1,0],[0,0,1],[1,0,0]]
Output: 5
Explanation: Two valid routes begin by moving right, and three begin by moving down.

Example 2

Input: grid = [[0,0],[0,0]]
Output: 2
Explanation: With no mirrors, the two routes are right then down and down then right.

Example 3

Input: grid = [[0,1,1],[1,1,0]]
Output: 1
Explanation: Moving right triggers reflections at (0,1) and (1,1), reaching (1,2). Moving down instead eventually sends the robot outside the grid.

3. 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

4. Solutions

Dynamic Programming

m = grid.size(), n = grid.front().size()
Time complexity: O(mn)
Space complexity: O(n)

 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

class Solution {
public:
    int uniquePaths(const vector<vector<int>> &grid) {
        const int m = grid.size(), n = grid.front().size();
        const int mod = 1e9 + 7;

        vector<pair<int, int>> ways(n, {0, 0}); // left, up
        ways.front() = {0, 1};
        for (int i = 1; i < n && grid[0][i - 1] == 0; ++i) {
            ways[i] = {1, 0};
        }

        for (int i = 1; i < m; ++i) {
            ways.front() = grid[i - 1][0] == 0 && ways.front() == pair<int, int>{0, 1}
                ? pair<int, int>{0, 1}
                : pair<int, int>{0, 0};

            for (int j = 1; j < n; ++j) {
                int backup = ways[j].first;

                ways[j].first =
                    ((grid[i][j - 1] == 1 ? 0 : ways[j - 1].first) + ways[j - 1].second) % mod;
                ways[j].second = ((grid[i - 1][j] == 1 ? 0 : ways[j].second) + backup) % mod;
            }
        }

        return (ways.back().first + ways.back().second) % mod;
    }
};