2026-01-29：统计镜子反射路径数目。用go语言，给定一个大小为 m × n 的二值网格 grid（0 表示空格，1 表示镜子）。机器人从左上角 (0,0) 出发，目标是到达右下角 (m−1,n

2026-01-29：统计镜子反射路径数目。用go语言，给定一个大小为 m × n 的二值网格 grid（0 表示空格，1 表示镜子）。机器人从左上角 (0,0) 出发，目标是到达右下角 (m−1,n−1)。机器人每步只能向右或向下移动，但如果准备进入的格子里有镜子，它不会直接进入，而是在进入前被“反射”改换方向并跳到镜子相应一格之外的位置：

• 若机器人想向右进入一个镜子格子，它会被转向向下并移动到该镜子的正下方格子；
• 若机器人想向下进入一个镜子格子，它会被转向向右并移动到该镜子的正右方格子。

如果这样的反射使机器人移出网格，则该路径无效，不计入答案。注意：若反射后到达的格子仍然是镜子，会立即按照进入时的方向再发生一次反射（反射方向由当次进入的移动方向决定）。求从起点到终点的所有不同有效路径数，并对 1000000007 取模返回结果。

m == grid.length。

n == grid[i].length。

2 <= m, n <= 500。

grid[i][j] 的值为 0 或 1。

grid[0][0] == grid[m - 1][n - 1] == 0。

输入： grid = [[0,1,0],[0,0,1],[1,0,0]]。

输出： 5。

解释：

[M] 表示机器人试图进入一个有镜子的格子但被反射了。

题目来自力扣3665。

算法过程描述

该算法采用动态规划，逐行处理网格，并维护一个状态数组来记录到达当前行各列的路径数。其核心在于通过两个状态来区分机器人进入某个格子时的移动方向。

1. 初始化
   • 定义模数 mod = 1_000_000_007 用于结果取模。
   • 获取网格的列数 n。
   • 创建状态数组 f，其大小为 n+1（索引从0到n）。数组的每个元素是一个包含两个整数的数组 [2]int：
     • f[j][0] 表示从上方格子移动到当前行第 j 列（即从 (i-1, j) 向下移动）的累计路径数。
     • f[j][1] 表示从左侧格子移动到当前行第 j 列（即从 (i, j-1) 向右移动）的累计路径数。
   • 初始化起点 (0,0) 的状态。由于机器人起点在 (0,0)，并且只能向右或向下移动，因此可以理解为存在一条“从上方来”的路径和一条“从左方来”的路径到达 (0,0)（尽管逻辑上起点没有前驱）。代码通过将 f[1]（对应第0列）初始化为 {1, 1} 来巧妙地设定初始状态。
2. 遍历网格
   • 外层循环遍历网格的每一行 row。
   • 内层循环遍历当前行的每一个格子 (i, j)，其值为 x（0或1）。
3. 状态转移（核心逻辑）
   对于每个格子 (i, j)，根据其是否为镜子（x 的值）更新状态 f[j+1]（因为 f 的索引从1开始，对应网格列索引0）：
   • 情况一：当前格子是空格 (x == 0)
     • f[j+1][0] 更新（来自上方的路径）：如果机器人从上方 (i-1, j) 向下移动进入这个空格，它可以继续向下一个格子移动。因此，到达此格子的路径数等于从上方到达当前格子的路径数 f[j][0] 加上从左侧到达当前格子的路径数 f[j+1][1]（因为从左侧进入空格后，方向不变，可以继续向右或向下，但这里 f[j+1][1] 已经包含了从左侧到达 (i, j) 的路径信息，用于更新当前状态）。代码中的逻辑是 f[j+1][0] = (f[j][0] + f[j+1][1]) % mod。
     • f[j+1][1] 更新（来自左侧的路径）：如果机器人从左侧 (i, j-1) 向右移动进入这个空格，其路径数与从上方进入的情况相同，因为空格不改变方向。所以 f[j+1][1] 被设置为与 f[j+1][0] 相同的值。
     • 简单来说，对于空格，无论从哪个方向进入，都能正常通过，因此到达该格子的路径数合并了来自上方和左侧的路径。
   • 情况二：当前格子是镜子 (x == 1)镜子格子的状态转移是算法最巧妙的部分，它通过交换和叠加状态来模拟反射行为，避免了显式地追踪反射跳转。
     • f[j+1][0] 更新（来自上方的路径）：如果机器人从上方 (i-1, j) 向下移动试图进入这个镜子格子，它会被反射。根据规则，向下进入镜子会被转向右，并移动到镜子正右方的格子 (i, j+1)。在动态规划的状态更新中，这个反射动作意味着：原本计划到达镜子格子 (i, j) 的路径（由 f[j][0] 表示），现在实际上被转移到了其右侧的格子 (i, j+1) 的“来自左侧的路径”上。因此，代码中 f[j+1][0] 的值被更新为 f[j+1][1]，可以理解为将上方来的路径“叠加”到右侧格子来自左侧的路径上。
     • f[j+1][1] 更新（来自左侧的路径）：如果机器人从左侧 (i, j-1) 向右移动试图进入这个镜子格子，它会被反射。根据规则，向右进入镜子会被转向下，并移动到镜子正下方的格子 (i+1, j)。在状态更新中，这个反射动作意味着：原本计划到达镜子格子 (i, j) 的路径（由 f[j+1][1] 表示），现在实际上被转移到了其下方格子。由于算法是逐行处理的，在计算当前行时，下方格子的状态尚未更新。因此，这里的更新 f[j+1][1] = f[j][0] 可以理解为一种状态传递或记录，确保在后续处理中能正确计算反射效果。更准确地说，它记录了由于反射，从左侧来的路径如何影响下方格子的状态。
4. 返回结果
   • 当所有行和列都处理完毕后，状态数组 f 的最后一个元素 f[n][0] 存储的就是从起点 (0,0) 到达终点 (m-1, n-1) 的所有不同有效路径数，并对 mod 取模后的结果。这里取 f[n][0] 是因为到达终点通常可以理解为是从上方（即终点所在行的上一行）移动下来的最后一步。

复杂度分析

• 时间复杂度：算法需要遍历网格中的每个格子一次，总共遍历 m * n 个格子。每个格子的处理都是常数时间的操作。因此，总的时间复杂度为 O(m * n)。
• 空间复杂度：算法使用了一个大小为 n+1 的状态数组 f，其中每个元素是两个整数。这个数组的大小只与列数 n 有关，与行数 m 无关。因此，总的额外空间复杂度为 O(n)。

Go完整代码如下：

package main import("fmt")funcuniquePaths(grid [][]int)(ans int){const mod =1_000_000_007 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 {if x ==0{ f[j+1][0]=(f[j][0]+ f[j+1][1])% mod f[j+1][1]= f[j+1][0]}else{ f[j+1][0]= f[j+1][1] f[j+1][1]= f[j][0]}}}return f[n][0]}funcmain(){ grid :=[][]int{{0,1,0},{0,0,1},{1,0,0}} result :=uniquePaths(grid) fmt.Println(result)}

Python完整代码如下：

# -*-coding:utf-8-*-defuniquePaths(grid): MOD =1_000_000_007 n =len(grid[0]) f =[[0,0]for _ inrange(n +1)] f[1]=[1,1]for row in grid:for j, x inenumerate(row):if x ==0: f[j +1][0]=(f[j][0]+ f[j +1][1])% MOD f[j +1][1]= f[j +1][0]else: f[j +1][0]= f[j +1][1] f[j +1][1]= f[j][0]return f[n][0]# 测试代码if __name__ =="__main__": grid =[[0,1,0],[0,0,1],[1,0,0]] result = uniquePaths(grid)print(result)

C++完整代码如下：

#include<iostream>#include<vector>usingnamespace std;intuniquePaths(vector<vector<int>>& grid){constint MOD =1'000'000'007;int n = grid[0].size(); vector<vector<int>>f(n +1,vector<int>(2,0)); f[1][0]=1; f[1][1]=1;for(auto& row : grid){for(int j =0; j < n; j++){int x = row[j];if(x ==0){ f[j +1][0]=(f[j][0]+ f[j +1][1])% MOD; f[j +1][1]= f[j +1][0];}else{ f[j +1][0]= f[j +1][1]; f[j +1][1]= f[j][0];}}}return f[n][0];}intmain(){ vector<vector<int>> grid ={{0,1,0},{0,0,1},{1,0,0}};int result =uniquePaths(grid); cout << result << endl;// 输出结果return0;}