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"
)

func uniquePaths(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]
}

func main() {
	grid := [][]int{{0, 1, 0}, {0, 0, 1}, {1, 0, 0}}
	result := uniquePaths(grid)
	fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

def uniquePaths(grid):
    MOD = 1_000_000_007
    n = len(grid[0])
    f = [[0, 0] for _ in range(n + 1)]
    f[1] = [1, 1]
    
    for row in grid:
        for j, x in enumerate(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>

using namespace std;

int uniquePaths(vector<vector<int>>& grid) {
    const int 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];
}

int main() {
    vector<vector<int>> grid = {
        {0, 1, 0},
        {0, 0, 1},
        {1, 0, 0}
    };

    int result = uniquePaths(grid);
    cout << result << endl;  // 输出结果

    return 0;
}