A mirror is never a cell the robot stands on; it is a redirect. Reframing it that way is what makes the counting tractable, because a move stops being one step and becomes an attempt to enter a cell followed by a bounce chain, and that chain is fully determined by two things: which cell you tried to enter and which way you were going. My first instinct was the textbook unique-paths DP with mirrors treated as walls. On example 1 that returns 1 where the answer is 5, and the reason is worth keeping: a mirror does not stop a path, it forwards it, and it forwards a rightward entry and a downward entry to two different cells, `(r+1, c)` and `(r, c+1)`. Walling mirrors off throws away four of the five paths on a 3x3 grid. So I precompute the redirect instead. `R[r][c]` is where the robot actually ends up when it tries to enter `(r,c)` moving right, `D[r][c]` is the same for moving down, both encoded as `r*n+c`, with `-1` meaning the bounce threw it off the grid. On an empty cell you land on the cell itself. On a mirror, `R[r][c] = D[r+1][c]` and `D[r][c] = R[r][c+1]`. The two tables are mutually recursive, but every reference moves to a strictly larger `r+c`, so one sweep with `r` and `c` both descending fills them in `O(mn)` with no recursion and no cycle check, and an off-grid `-1` propagates back up the chain for free. After that the count is two transitions per occupied cell: `dp[r][c]` feeds `R[r][c+1]` and `D[r+1][c]`. Every landing cell sits strictly later in row-major order than its source, so ascending loops are already a valid topological order. Direction never enters the DP state. Once the robot stands on an empty cell both moves are open again, and the direction exists only inside a bounce chain. ## Worked example `grid = [[0,1,0],[0,0,1],[1,0,0]]`, so mirrors sit at `(0,1)`, `(1,2)` and `(2,0)`. The interesting table entries: `R[0][1] = D[1][1] = (1,1)`, so stepping right out of the start does not land on `(0,1)` at all. `D[2][0] = R[2][1] = (2,1)`, while `R[2][0]` wants row 3 and is `-1`. `R[1][2] = D[2][2] = (2,2)`. Now the sweep. `dp[0][0] = 1` sends 1 right into `(1,1)` and 1 down into `(1,0)`. From `(1,0)` the right move adds 1 to `(1,1)`, giving 2, and the down move bounces off the mirror at `(2,0)` into `(2,1)`, giving 1. From `(1,1)` with 2, right bounces off `(1,2)` into `(2,2)`, giving 2, and down adds 2 to `(2,1)`, giving 3. From `(2,1)` with 3, right lands on `(2,2)` for a total of 5, and down falls off the grid and is dropped. Answer 5. ## Complexity - Time O(mn) — one descending sweep builds both redirect tables, then each cell fires exactly two `O(1)` transitions. - Space O(mn) — two `int` redirect tables plus the counting layer; at the 500x500 limit that is a few megabytes. ## Code (C++) ```cpp class Solution { public: int uniquePaths(vector>& grid) { const long long MOD = 1000000007; int m = grid.size(), n = grid[0].size(); // R[r][c] = cell you actually end up in when you try to ENTER (r,c) moving right, // D[r][c] = the same for moving down; -1 means the bounce throws you out of the grid. vector> R(m, vector(n, -1)), D(m, vector(n, -1)); for (int r = m - 1; r >= 0; --r) { for (int c = n - 1; c >= 0; --c) { if (grid[r][c] == 0) { R[r][c] = D[r][c] = r * n + c; } else { R[r][c] = (r + 1 < m) ? D[r + 1][c] : -1; // right into a mirror -> pushed down D[r][c] = (c + 1 < n) ? R[r][c + 1] : -1; // down into a mirror -> pushed right } } } vector> dp(m, vector(n, 0)); dp[0][0] = 1; int last = (m - 1) * n + (n - 1); for (int r = 0; r < m; ++r) { for (int c = 0; c < n; ++c) { long long w = dp[r][c]; if (w == 0 || r * n + c == last) continue; int t = (c + 1 < n) ? R[r][c + 1] : -1; if (t >= 0) dp[t / n][t % n] = (dp[t / n][t % n] + w) % MOD; t = (r + 1 < m) ? D[r + 1][c] : -1; if (t >= 0) dp[t / n][t % n] = (dp[t / n][t % n] + w) % MOD; } } return (int)dp[m - 1][n - 1]; } }; ``` ## One note The off-grid rule applies to the bounce, not to the move, and that asymmetry is the whole trap. In example 1 the mirror at `(2,0)` is harmless when you enter it going down, since it spits you out at `(2,1)`; entering the same mirror going right would need row 3 and kills the path. Same cell, same mirror, one direction fine and one direction fatal. A single "can I enter this cell" predicate cannot express that, which is why there are two tables and not one. Example 3, `[[0,1,1],[1,1,0]]` with answer 1, is the compact demonstration: going down first runs `(0,0) -> (1,0)` mirror `-> (1,1)` mirror `-> ` row 2, which does not exist, so that entire branch is worth zero while the right-first branch survives. Transferable: when a single step in a grid problem resolves to a deterministic chain, precompute the chain as a function of cell plus entry state and the counting layer collapses back into the plain DP you already know how to write. Encoding the result as `r*n+c` with `-1` for invalid is what keeps that cheap, because then `t >= 0` is the only validity check left in the hot loop.