DeepSeek LeetCode 2617. 网格图中最少访问的格子数 TypeScript实现

以下是 LeetCode 2617「网格图中最少访问的格子数」的 TypeScript 实现，采用 BFS + 并查集（路径压缩） 优化，保证每个格子只被访问一次，时间复杂度 O(mn·α(mn))，空间复杂度 O(mn)。

```typescript
function minimumVisitedCells(grid: number[][]): number {
const m = grid.length, n = grid[0].length;
if (m === 1 && n === 1) return 1;

// 距离数组，-1 表示未访问
const dist: number[][] = Array.from({ length: m }, () => new Array(n).fill(-1));
dist[0][0] = 1;

// 行并查集：rowParent[i][j] 表示在第 i 行中，列 j 及之后下一个未访问的列
const rowParent: number[][] = Array.from({ length: m }, () => new Array(n + 1).fill(0));
// 列并查集：colParent[j][i] 表示在第 j 列中，行 i 及之后下一个未访问的行
const colParent: number[][] = Array.from({ length: n }, () => new Array(m + 1).fill(0));

// 初始化并查集，每个位置指向自身
for (let i = 0; i < m; i++) {
for (let j = 0; j <= n; j++) rowParent[i][j] = j;
}
for (let j = 0; j < n; j++) {
for (let i = 0; i <= m; i++) colParent[j][i] = i;
}

// 查找 + 路径压缩
const findRow = (i: number, j: number): number => {
if (rowParent[i][j] !== j) {
rowParent[i][j] = findRow(i, rowParent[i][j]);
}
return rowParent[i][j];
};
const findCol = (j: number, i: number): number => {
if (colParent[j][i] !== i) {
colParent[j][i] = findCol(j, colParent[j][i]);
}
return colParent[j][i];
};

// 标记某格子已被访问（从并查集中移除）
const unionRow = (i: number, j: number) => {
rowParent[i][j] = findRow(i, j + 1);
};
const unionCol = (j: number, i: number) => {
colParent[j][i] = findCol(j, i + 1);
};

// 起点标记为已使用
unionRow(0, 0);
unionCol(0, 0);

const queue: [number, number][] = [[0, 0]];

while (queue.length) {
const [i, j] = queue.shift()!;
const step = dist[i][j];
const maxRight = Math.min(n - 1, j + grid[i][j]);
const maxDown = Math.min(m - 1, i + grid[i][j]);

// 向右移动（同一行）
let col = findRow(i, j + 1);
while (col <= maxRight) {
dist[i][col] = step + 1;
if (i === m - 1 && col === n - 1) return dist[i][col];
queue.push([i, col]);
unionRow(i, col);
unionCol(col, i);
col = findRow(i, col + 1);
}

// 向下移动（同一列）
let row = findCol(j, i + 1);
while (row <= maxDown) {
dist[row][j] = step + 1;
if (row === m - 1 && j === n - 1) return dist[row][j];
queue.push([row, j]);
unionRow(row, j);
unionCol(j, row);
row = findCol(j, row + 1);
}
}

return dist[m - 1][n - 1];
}
```

核心思路

· BFS 层次遍历：每次移动代价为 1，首次到达 (m-1, n-1) 时即为最少步数。
· 并查集跳过已访问格子：
· 对每一行维护一个并查集 rowParent，指向下一个未访问的列。
· 对每一列维护一个并查集 colParent，指向下一个未访问的行。
· 查找操作 findRow / findCol 配合路径压缩，能快速跳过已被访问的格子。
· 双向标记：当一个格子 (r, c) 被访问后，同时从行并查集和列并查集中移除，确保不会被重复处理。

复杂度分析

· 时间复杂度：O(mn·α(mn))，其中 α 为阿克曼反函数，近似常数。每个格子最多被访问一次，并查集操作几乎为常数。
· 空间复杂度：O(mn)，用于存储距离数组、两个并查集以及 BFS 队列。