统计镜子反射路径数目【力扣LeetCode & 每日一题】

3665. 统计镜子反射路径数目

网页链接

力扣LeetCode

力扣LeetCode & 每日一题，完成每日打卡，即可获得力扣积分。获得相应数量的积分，能在【力扣商店】，换取相应奖品！助力每日有题做，丰盈积分日益多！

题目描述

给你一个 m x n 的二进制网格 grid，其中：

• grid[i][j] == 0 表示一个空格子。
• grid[i][j] == 1 表示一面镜子。

一个机器人从网格的左上角 (0, 0) 出发，想要到达右下角 (m – 1, n – 1)。它只能向 右 或向 下 移动。如果机器人试图移入一个有镜子的格子，它会在进入该格子前被 反射：

• 如果它试图向 右 移动进入镜子，它会被转向 下 方，并移动到镜子正下方。
• 如果它试图向 下 移动进入镜子，它会被转向 右 方，并移动到镜子正右方。

如果这次反射会导致机器人移动到网格边界之外，则该路径被视为无效，不应被计数。

返回从 (0, 0) 到 (m – 1, n – 1) 不同的有效路径数量。

由于答案可能非常大，请将其返回对

10

9

+

7

10^9 + 7

109+7 取模 的结果。

注意： 如果一次反射将机器人移动到一个有镜子的格子，机器人会立即再次被反射。这次反射的方向取决于它进入该镜子的方向：如果它是向右移动进入的，它将被转向下方；如果它是向下移动进入的，它将被转向右方。

输入描述

一个 m x n 的二进制网格 grid，grid[i][j] 的值为 0（空格子）或 1（镜子）。

输出描述

返回从 (0, 0) 到 (m – 1, n – 1) 的有效路径数量，结果对

10

9

+

7

10^9 + 7

109+7 取模。

示例

示例 1

输入：

grid = [[0,1,0],[0,0,1],[1,0,0]]

输出：

5

解释：

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

示例 2

输入：

grid = [[0,0],[0,0]]

输出：

2

解释：

示例 3

输入：

grid = [[0,1,1],[1,1,0]]

输出：

1

解释：

(0, 0) → (1, 0) [M] → (1, 1) [M] → (2, 1) 超出边界，因此是无效路径。

数据范围

• m == grid.length
• n == grid[i].length
• $2\le m,n\le 500$
• grid[i][j] 的值为 0 或 1
• grid[0][0] == grid[m – 1][n – 1] == 0

解题思路

本题是网格轮廓线动态规划 + 方向流状态问题。机器人从 (0,0) 出发，每次只能向右或向下移动。遇到空格子 0 时可以继续向右或向下；遇到镜子 1 时不能进入，而是发生反射：从左边向右进入的路径会转向下，从上边向下进入的路径会转向右。因此，每个格子的关键信息不是“到达该格子的路径数”，而是“从该格子向右流出的路径数”和“从该格子向下流出的路径数”。利用按行从左到右扫描，可以用一维滚动数组维护当前轮廓上的方向流。

1. 状态定义

设 f[j+1][0] 和 f[j+1][1] 分别表示当前格子 (i,j) 处理完毕后：

• f[j+1][0]：从 (i,j) 向右流出的路径数；
• f[j+1][1]：从 (i,j) 向下流出的路径数。

在扫描到格子 (i,j) 之前，数组 f 中：

• f[j][0] 表示从左边 (i,j-1) 向右流入当前格子的路径数；
• f[j+1][1] 表示从上边 (i-1,j) 向下流入当前格子的路径数。

因此，当前格子的总流入路径数为：

f

[

j

]

[

0

]

+

f

[

j

+

1

]

[

1

]

f[j][0] + f[j+1][1]

f[j][0]+f[j+1][1]

2. 空格子的转移

若 grid[i][j] == 0，机器人可以在该格选择继续向右或向下。因此流入的总路径数会同时分配给两个出口：

f

[

j

+

1

]

[

0

]

=

f

[

j

]

[

0

]

+

f

[

j

+

1

]

[

1

]

f[j+1][0] = f[j][0] + f[j+1][1]

f[j+1][0]=f[j][0]+f[j+1][1]

f

[

j

+

1

]

[

1

]

=

f

[

j

+

1

]

[

0

]

f[j+1][1] = f[j+1][0]

f[j+1][1]=f[j+1][0]

也就是说，从该格子向右流出的路径数和向下流出的路径数都等于流入总路径数。

3. 镜子格子的转移

若 grid[i][j] == 1，机器人不能进入，只能发生反射：

• 从左边向右流入的路径会被转向下，因此变成向下流出；
• 从上边向下流入的路径会被转向右，因此变成向右流出。

于是：

f

[

j

+

1

]

[

0

]

=

f

[

j

+

1

]

[

1

]

f[j+1][0] = f[j+1][1]

f[j+1][0]=f[j+1][1]

f

[

j

+

1

]

[

1

]

=

f

[

j

]

[

0

]

f[j+1][1] = f[j][0]

f[j+1][1]=f[j][0]

即两个方向的流发生交换。

4. 初始化

起点 (0,0) 是空格子。为了产生从起点向右和向下的初始路径，初始化：

f[1] = {1, 1};

这等价于在起点处有一个“流入”的路径，并按空格子规则分叉为向右和向下各一条路径。其余位置初始为 0。

5. 答案

按行从上到下、每行从左到右处理所有格子。终点 (m-1,n-1) 也是空格子。处理完终点后，f[n][0] 就是到达终点的总路径数，即答案。返回前对

10

9

+

7

10^9+7

109+7 取模。

6. 正确性说明

每个格子的状态只依赖于其左方和上方的方向流。空格子允许路径继续向右或向下，因此流入总路径数同时贡献给两个方向；镜子强制转向，因此左来流变为向下，上来流变为向右。按行扫描时，f[j][0] 正是左方格子的向右流，f[j+1][1] 正是上方格子的向下流，二者恰好覆盖所有可能进入当前格子的路径。因此转移完整且不重不漏。

7. 复杂度分析

• 时间复杂度：$O(mn)$
• 空间复杂度：$O(n)$

总结

用两个状态分别记录每个格子向右和向下流出的路径数。空格子将流入总路径数同时传给两个方向；镜子则将左来流与上来流交换方向。按行从左到右滚动更新，最终 f[n][0] 即为从左上角到右下角的有效路径数。整体是

O

(

m

n

)

O(mn)

O(mn) 时间、

O

(

n

)

O(n)

O(n) 空间的轮廓线动态规划。

代码内容

class Solution {
public:
int uniquePaths(vector<vector<int>>& g) {
const int M = 1'000'000'007;
int n = g[0].size();
vector<array<int, 2>> f(n + 1);
f[1] = {1, 1};
for (auto& row : g) {
for (int j = 0; j < n; j++) {
if (row[j] == 0) {
f[j + 1][0] = (f[j][0] + f[j + 1][1]) % M;
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];
}
};