Medium
题目描述
给定一个 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 取模的值。
注意：如果反射将机器人移动到另一个镜子格子，机器人会根据进入该镜子的方向立即再次反射：如果它是向右进入的，会被转向下方；如果它是向下进入的，会被转向右方。这个过程会继续，直到到达最后一个格子、机器人移出边界或机器人移动到非镜子格子。
示例 1：
输入：grid = [[0,1,0],[0,0,1],[1,0,0]]
输出：5
示例 2：
输入：grid = [[0,0],[0,0]]
输出：2
示例 3：
输入：grid = [[0,1,1],[1,1,0]]
输出：1
约束：
- 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
解题思路
这是一道动态规划题目，关键在于处理镜子的反射机制。
核心思路：
预计算跳跃目标：对于每个位置 (i,j) 和每个移动方向（右/下），预计算如果下一步遇到镜子时实际会到达的位置。这样可以避免在DP过程中重复计算反射链。
动态规划状态定义：
dp[i][j]表示到达位置 (i,j) 的路径数量。状态转移：
- 初始化：
dp[0][0] = 1 - 对于每个位置 (i,j)，如果
dp[i][j] > 0，则将其贡献传递给两个可能的下一步位置（通过预计算的跳跃表）
- 初始化：
反射处理：
- 向右遇到镜子：转向下方
- 向下遇到镜子：转向右方
- 连续反射直到到达非镜子格子或出界
算法步骤：
- 预计算每个位置每个方向的实际到达位置
- 使用动态规划计算路径数
- 对所有运算结果取模
这种方法将复杂的反射逻辑预处理，使得DP过程变得简洁高效。
代码实现
class Solution {
public:
int uniquePaths(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
const int MOD = 1e9 + 7;
// go[i][j][0] = 从(i,j)向右移动的实际到达位置
// go[i][j][1] = 从(i,j)向下移动的实际到达位置
vector<vector<vector<pair<int,int>>>> go(m, vector<vector<pair<int,int>>>(n, vector<pair<int,int>>(2, {-1, -1})));
// 预计算每个位置每个方向的跳跃目标
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
// 向右移动
if (j + 1 < n) {
int x = i, y = j + 1;
int dir = 0; // 0=right, 1=down
while (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1) {
if (dir == 0) { // 向右遇到镜子，转向下
x++;
dir = 1;
} else { // 向下遇到镜子，转向右
y++;
dir = 0;
}
}
if (x >= 0 && x < m && y >= 0 && y < n) {
go[i][j][0] = {x, y};
}
}
// 向下移动
if (i + 1 < m) {
int x = i + 1, y = j;
int dir = 1; // 0=right, 1=down
while (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1) {
if (dir == 0) { // 向右遇到镜子，转向下
x++;
dir = 1;
} else { // 向下遇到镜子，转向右
y++;
dir = 0;
}
}
if (x >= 0 && x < m && y >= 0 && y < n) {
go[i][j][1] = {x, y};
}
}
}
}
// 动态规划
vector<vector<long long>> dp(m, vector<long long>(n, 0));
dp[0][0] = 1;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (dp[i][j] > 0) {
// 向右移动
if (go[i][j][0].first != -1) {
int x = go[i][j][0].first, y = go[i][j][0].second;
dp[x][y] = (dp[x][y] + dp[i][j]) % MOD;
}
// 向下移动
if (go[i][j][1].first != -1) {
int x = go[i][j][1].first, y = go[i][j][1].second;
dp[x][y] = (dp[x][y] + dp[i][j]) % MOD;
}
}
}
}
return dp[m-1][n-1];
}
};
class Solution:
def uniquePaths(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
MOD = 10**9 + 7
# go[i][j][0] = 从(i,j)向右移动的实际到达位置
# go[i][j][1] = 从(i,j)向下移动的实际到达位置
go = [[[-1, -1] for _ in range(2)] for _ in range(n)] for _ in range(m)]
# 预计算每个位置每个方向的跳跃目标
for i in range(m):
for j in range(n):
# 向右移动
if j + 1 < n:
x, y = i, j + 1
direction = 0 # 0=right, 1=down
while 0 <= x < m and 0 <= y < n and grid[x][y] == 1:
if direction == 0: # 向右遇到镜子，转向下
x += 1
direction = 1
else: # 向下遇到镜子，转向右
y += 1
direction = 0
if 0 <= x < m and 0 <= y < n:
go[i][j][0] = [x, y]
# 向下移动
if i + 1 < m:
x, y = i + 1, j
direction = 1 # 0=right, 1=down
while 0 <= x < m and 0 <= y < n and grid[x][y] == 1:
if direction == 0: # 向右遇到镜子，转向下
x += 1
direction = 1
else: # 向下遇到镜子，转向右
y += 1
direction = 0
if 0 <= x < m and 0 <= y < n:
go[i][j][1] = [x, y]
# 动态规划
dp = [[0] * n for _ in range(m)]
dp[0][0] = 1
for i in range(m):
for j in range(n):
if dp[i][j] > 0:
# 向右移动
if go[i][j][0][0] != -1:
x, y = go[i][j][0]
dp[x][y] = (dp[x][y] + dp[i][j]) % MOD
# 向下移动
if go[i][j][1][0] != -1:
x, y = go[i][j][1]
dp[x][y] = (dp[x][y] + dp[i][j]) % MOD
return dp[m-1][n-1]
public class Solution {
public int UniquePaths(int[][] grid) {
int m = grid.Length, n = grid[0].Length;
const int MOD = 1000000007;
// go[i,j,0] = 从(i,j)向右移动的实际到达位置
// go[i,j,1] = 从(i,j)向下移动的实际到达位置
int[,,] go = new int[m, n, 4]; // [x, y] for each direction
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
go[i, j, 0] = go[i, j, 2] = -1; // 初始化为-1表示无效
}
}
// 预计算每个位置每个方向的跳跃目标
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
// 向右移动
if (j + 1 < n) {
int x = i, y = j + 1;
int dir = 0; // 0=right, 1=down
while (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1) {
if (dir == 0) { // 向右遇到镜子，转向下
x++;
dir = 1;
} else { // 向下遇到镜子，转向右
y++;
dir = 0;
}
}
if (x >= 0 && x < m && y >= 0 && y < n) {
go[i, j, 0] = x;
go[i, j, 1] = y;
}
}
// 向下移动
if (i + 1 < m) {
int x = i + 1, y = j;
int dir = 1; // 0=right, 1=down
while (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1) {
if (dir == 0) { // 向右遇到镜子，转向下
x++;
dir = 1;
} else { // 向下遇到镜子，转向右
y++;
dir = 0;
}
}
if (x >= 0 && x < m && y >= 0 && y < n) {
go[i, j, 2] = x;
go[i, j, 3] = y;
}
}
}
}
// 动态规划
long[,] dp = new long[m, n];
dp[0, 0] = 1;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (dp[i, j] > 0) {
// 向右移动
if (go[i, j, 0] != -1) {
int x = go[i, j, 0], y = go[i, j, 1];
dp[x, y] = (dp[x, y] + dp[i, j]) % MOD;
}
// 向下移动
if (go[i, j, 2] != -1) {
int x = go[i, j, 2], y = go[i, j, 3];
dp[x, y] = (dp[x, y] + dp[i, j]) % MOD;
}
}
}
}
return (int)dp[m-1, n-1];
}
}
var uniquePaths = function(grid) {
const MOD = 1000000007;
const m = grid.length;
const n = grid[0].length;
const memo = new Map();
function getKey(r, c, dir) {
return `${r},${c},${dir}`;
}
function dfs(r, c, dir) {
if (r < 0 || r >= m || c < 0 || c >= n) {
return 0;
}
if (r === m - 1 && c === n - 1) {
return 1;
}
const key = getKey(r, c, dir);
if (memo.has(key)) {
return memo.get(key);
}
let result = 0;
if (grid[r][c] === 1) {
if (dir === 0) {
result = dfs(r + 1, c, 1);
} else {
result = dfs(r, c + 1, 0);
}
} else {
result = (dfs(r, c + 1, 0) + dfs(r + 1, c, 1)) % MOD;
}
memo.set(key, result);
return result;
}
return dfs(0, 0, -1);
};
复杂度分析
| 指标 | 复杂度 |
|---|---|
| 时间 | - |
| 空间 | - |