LeetCode 3797. 统计在矩形格子里移动的路径数目 — TypeScript 实现

思路

状态定义（从下往上递推）：

- `f[i][j]`：到达 `(i, j)`，且最后一步是从下一行纵向移动上来的路径数
- `g[i][j]`：到达 `(i, j)`，且最后一步是同一行横向移动来的路径数

转移方程：

1. 纵向移动（从 `(i+1, j')` 到 `(i, j)`）：
要求 `√(1 + (j-j')²) ≤ d`，即 `|j-j'| ≤ √(d²-1)`。记 `k = ⌊√(d²-1)⌋`。

```
f[i][j] = Σ(f[i+1][j'] + g[i+1][j'])，j' ∈ [j-k, j+k]
```

2. 横向移动（从 `(i, j')` 到 `(i, j)`）：
要求 `|j-j'| ≤ d` 且 `j' ≠ j`。关键限制：不能连续两次横向移动，所以横向移动的前一步必须是从下一行上来的。

```
g[i][j] = Σ(f[i][j'])，j' ∈ [j-d, j+d] 且 j' ≠ j
```

3. 初始化：最后一行每个空地作为起点，`f[n-1][j] = 1`

两个转移都是区间求和，用前缀和优化到 `O(1)`，总复杂度 `O(n·m)`。

---

TypeScript 代码

```typescript
function numberOfRoutes(grid: string[], d: number): number {
const MOD = 1_000_000_007;
const n = grid.length;
const m = grid[0].length;
// 纵向移动时，横向最大偏移：floor(sqrt(d^2 - 1))
const k = Math.floor(Math.sqrt(d * d - 1));

// prefix[i][j][0]: 第 i 行前 j 个位置（0~j-1）的 f 之和
// prefix[i][j][1]: 第 i 行前 j 个位置（0~j-1）的 g 之和
const prefix: number[][][] = Array.from({ length: n }, () =>
Array.from({ length: m + 1 }, () => [0, 0])
);

const add = (a: number, b: number): number => (a + b) % MOD;
const sub = (a: number, b: number): number => (a - b + MOD) % MOD;

for (let i = n - 1; i >= 0; i--) {
// 1. 计算 f[i][j]：从下一行上来
for (let j = 0; j < m; j++) {
if (grid[i][j] === '.') {
if (i === n - 1) {
// 最后一行作为起点
prefix[i][j + 1][0] = add(prefix[i][j][0], 1);
} else {
const l = Math.max(j - k, 0);
const r = Math.min(j + k, m - 1);
const sumF = sub(prefix[i + 1][r + 1][0], prefix[i + 1][l][0]);
const sumG = sub(prefix[i + 1][r + 1][1], prefix[i + 1][l][1]);
const curr = add(sumF, sumG);
prefix[i][j + 1][0] = add(prefix[i][j][0], curr);
}
} else {
// 障碍物，前缀和不变
prefix[i][j + 1][0] = prefix[i][j][0];
}
}

// 2. 计算 g[i][j]：同一行横向移动
// 只能从上一步是"从下一行上来"的状态转移（不能连续横向）
for (let j = 0; j < m; j++) {
if (grid[i][j] === '.') {
const l = Math.max(j - d, 0);
const r = Math.min(j + d, m - 1);
// 排除 j 本身，拆成 [l, j-1] 和 [j+1, r] 两段
let left = 0, right = 0;
if (l <= j - 1) {
left = sub(prefix[i][j][0], prefix[i][l][0]);
}
if (j + 1 <= r) {
right = sub(prefix[i][r + 1][0], prefix[i][j + 1][0]);
}
const curr = add(left, right);
prefix[i][j + 1][1] = add(prefix[i][j][1], curr);
} else {
prefix[i][j + 1][1] = prefix[i][j][1];
}
}
}

// 第 0 行所有可用格子的 f + g 之和
return add(prefix[0][m][0], prefix[0][m][1]);
}
```

---

复杂度

项目 复杂度
时间 `O(n × m)`
空间 `O(n × m)`（可滚动优化至 `O(m)`）