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

以下是 LeetCode 2617「网格图中最少访问的格子数」的 TypeScript 实现采用 BFS 并查集路径压缩 优化保证每个格子只被访问一次时间复杂度 O(mn·α(mn))空间复杂度 O(mn)。typescriptfunction 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 队列。