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。

算法过程描述

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

复杂度分析

• 时间复杂度：算法需要遍历网格中的每个格子一次，总共遍历 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;
}