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。
解释：
| 编号 | 完整路径 |
|---|---|
| 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] 表示机器人试图进入一个有镜子的格子但被反射了。
题目来自力扣3665。
算法过程描述
该算法采用动态规划，逐行处理网格，并维护一个状态数组来记录到达当前行各列的路径数。其核心在于通过两个状态来区分机器人进入某个格子时的移动方向。
- 初始化
- 定义模数
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}来巧妙地设定初始状态。
- 定义模数
- 遍历网格
- 外层循环遍历网格的每一行
row。 - 内层循环遍历当前行的每一个格子
(i, j)，其值为x（0或1）。
- 外层循环遍历网格的每一行
- 状态转移（核心逻辑）
对于每个格子(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]可以理解为一种状态传递或记录，确保在后续处理中能正确计算反射效果。更准确地说，它记录了由于反射，从左侧来的路径如何影响下方格子的状态。
- 情况一：当前格子是空格 (
- 返回结果
- 当所有行和列都处理完毕后，状态数组
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;}
