LeetCode 中等题：扭曲镜面路径计数 Twisted Mirror Path Count

题目链接：https://leetcode.cn/problems/twisted-mirror-path-count/
难度：中等
标签：动态规划、DAG、记忆化跳转

题目描述

给你一个 m x n 的二进制网格 grid：

• grid[i][j] == 0：空格子
• grid[i][j] == 1：镜子

机器人从左上角 (0,0) 出发，目标是右下角 (m-1, n-1)。
机器人只能尝试向右或者向下发起移动，不能随便改方向。

镜面反射核心规则（本题最容易理解错的地方）

当机器人试图移入镜子格子时，不会进入镜子，在进入前触发反射：

1. 原本尝试向右移动撞镜子 → 转向向下，尝试移动到镜子正下方
2. 原本尝试向下移动撞镜子 → 转向向右，尝试移动到镜子正右方

额外规则：

• 连锁反射：反射之后，如果新目标依然是镜子，立刻再次反射，方向由当前进入镜子的方向决定
• 如果反射链条最终落点越出网格边界 → 这条移动无效，不计入路径
• 只有最终落在合法空格上，才算完成本次移动
• grid[0][0] 和 grid[m-1][n-1] 保证为 0
• 答案对 (10^9+7) 取模
• 数据范围：(2 \le m,n \le 500)

示例 1

grid = [[0,1,0],[0,0,1],[1,0,0]]
输出：5

解释：一共 5 条有效路径，[M] 代表尝试进入镜子触发反射

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)

示例 2

grid = [[0,0],[0,0]]
输出：2

没有镜子，就是经典只能向右、向下走的网格路径总数。

示例 3

grid = [[0,1,1],[1,1,0]]
输出：1

其中一条路径经过连续反射后走出边界，直接作废，只剩一条合法路径。

思路分析

为什么不能 DFS / BFS？

网格最大是 500 × 500，共 250000 个格子。暴力搜索枚举所有路径是指数级复杂度，直接超时。
这是典型的路径计数问题，优先考虑动态规划。

DP 状态定义

dp[i][j]：到达空格 (i,j) 的有效路径数量

• 初始条件：dp[0][0] = 1，起点有一种方案
• 答案：dp[m-1][n-1]

和普通网格 DP 的区别：
普通网格：在 (i,j) 向右走一步直接到 (i,j+1)，向下一步直接到 (i+1,j)
本题：向右 / 向下只是发起移动的方向，中间可能触发一连串镜面偏转，最终落点不确定。

核心子函数：jump 跳转函数

我们封装一个跳转函数 jump(r, c, d)：
从空格 (r,c)，尝试朝方向 d（0 向右，1 向下）发起移动，沿着镜面连锁反射，直到：

1. 落点越界 → 返回 None，本次移动无效
2. 落在空格 → 返回最终坐标 (nr, nc)

因为网格镜子固定不变，同一个位置 + 同一个方向的跳转结果永远一样，我们增加缓存 cache，避免重复循环反射，保证效率。

DP 转移流程

遍历网格，对于每一个有路径数的格子 (i,j)：

1. 尝试向右发起移动：调用 jump，拿到最终落点。落点合法则 dp[落点] += dp[i][j]
2. 尝试向下发起移动：调用 jump，拿到最终落点。落点合法则 dp[落点] += dp[i][j]
   每次加法后对 1e9+7 取模。

遍历顺序：从上到下、从左到右行优先遍历即可。因为所有跳转后的落点坐标一定不会比起点更靠左、更靠上，天然满足 DAG 无后效性。

复杂度分析

• 预处理跳转缓存：每个位置两个方向最多计算一次，(O(mn))
• DP 遍历：(O(mn))
  500 × 500 的规模完全可以轻松通过。

Python 代码实现

MOD = 10**9 + 7

class Solution:
    def twistedMirrorPathCount(self, grid: list[list[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        # dir: 0 向右，1 向下
        # cache[r][c][d] 缓存跳转结果，越界为 None
        cache = [[[None] * 2 for _ in range(n)] for __ in range(m)]

        def jump(r: int, c: int, d: int):
            if cache[r][c][d] is not None:
                return cache[r][c][d]
            cr, cc, cd = r, c, d
            while True:
                if cd == 0:
                    # 当前尝试向右撞击
                    nr, nc = cr, cc + 1
                else:
                    # 当前尝试向下撞击
                    nr, nc = cr + 1, cc
                # 越界，无效
                if not (0 <= nr < m and 0 <= nc < n):
                    cache[r][c][d] = None
                    return None
                # 落到空格，跳转结束
                if grid[nr][nc] == 0:
                    cache[r][c][d] = (nr, nc)
                    return (nr, nc)
                # 撞到镜子，反射，切换方向，继续循环
                newd = 1 if cd == 0 else 0
                cr, cc, cd = nr, nc, newd

        dp = [[0] * n for _ in range(n)]
        dp[0][0] = 1

        for i in range(m):
            for j in range(n):
                if dp[i][j] == 0:
                    continue
                # 尝试向右移动
                res = jump(i, j, 0)
                if res is not None:
                    ni, nj = res
                    dp[ni][nj] = (dp[ni][nj] + dp[i][j]) % MOD
                # 尝试向下移动
                res = jump(i, j, 1)
                if res is not None:
                    ni, nj = res
                    dp[ni][nj] = (dp[ni][nj] + dp[i][j]) % MOD
        return dp[m-1][n-1] % MOD

踩坑清单（博客重点）

1. ❌ 误区：机器人可以站在镜子格子里

镜子不能进入，是尝试进入的一瞬间发生反射。

2. ❌ 误区：反射只反射一次

题目明确支持连续连锁反射，必须 while 循环直到空格或者出界。

3. ❌ 误区：DP 直接 i,j+1、i+1,j

这是最多人写错的地方，向右 / 向下只是发起方向，不是最终落点。

4. ❌ 误区：不做缓存，每次 jump 都循环反射

同一个点同一个方向反复跳转，会大量重复计算导致超时。

5. ❌ 误区：反射出界之后依然计数

只要跳转链条最后越界，这条移动直接作废，不能给 dp 贡献数值。

总结

这道题是经典网格路径 DP 的变种题，核心思想可以一句话概括：

镜子的作用是把「一次移动」从一步相邻格子，替换成一条固定的偏转跳转链路。
我们先把跳转关系预处理映射好，问题就退化成普通 DAG 上的路径计数 DP。