2026-01-29：统计镜子反射路径数目。用go语言，给定一个大小为 m × n 的二值网格 grid（0 表示空格，1 表示镜子）。机器人从左上角 (0,0) 出发，目标是到达右下角 (m−1,n−1)。机器人每步只能向右或向下移动，但如果准备进入的格子里有镜子，它不会直接进入，而是在进入前被“反射”改换方向并跳到镜子相应一格之外的位置：
• 若机器人想向右进入一个镜子格子，它会被转向向下并移动到该镜子的正下方格子；
• 若机器人想向下进入一个镜子格子，它会被转向向右并移动到该镜子的正右方格子。
如果这样的反射使机器人移出网格，则该路径无效，不计入答案。注意：若反射后到达的格子仍然是镜子，会立即按照进入时的方向再发生一次反射（反射方向由当次进入的移动方向决定）。求从起点到终点的所有不同有效路径数，并对 1000000007 取模返回结果。
m == grid.length。
n == grid[i].length。
2
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。
算法过程描述
该算法采用动态规划，逐行处理网格，并维护一个状态数组来记录到达当前行各列的路径数。其核心在于通过两个状态来区分机器人进入某个格子时的移动方向。
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
#include
using namespace std;
int uniquePaths(vector>& grid) {
const int MOD = 1'000'000'007;
int n = grid[0].size;
vector> f(n + 1, vector(2, 0));
f[1][0] = 1;
f[1][1] = 1;
for (auto& row : grid) {
for (int j = 0; 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> grid = {
{0, 1, 0},
{0, 0, 1},
};
int result = uniquePaths(grid);
cout
return 0;
}
我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。
欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。