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

以下是 LeetCode 2617「网格图中最少访问的格子数」的 Java 实现采用 BFS TreeSet 优化保证每个格子只被访问一次时间复杂度 O(mn log(mn))。javaclass Solution {public int minimumVisitedCells(int[][] grid) {int m grid.length, n grid[0].length;if (m 1 n 1) return 1;// 距离数组-1 表示未访问int[][] dist new int[m][n];for (int i 0; i m; i) Arrays.fill(dist[i], -1);dist[0][0] 1;// 每一行未访问的列索引TreeSetInteger[] rows new TreeSet[m];// 每一列未访问的行索引TreeSetInteger[] cols new TreeSet[n];for (int i 0; i m; i) rows[i] new TreeSet();for (int j 0; j n; j) cols[j] new TreeSet();// 初始化所有格子除起点外加入集合for (int i 0; i m; i) {for (int j 0; j n; j) {if (i 0 j 0) continue;rows[i].add(j);cols[j].add(i);}}Queueint[] queue new LinkedList();queue.offer(new int[]{0, 0});while (!queue.isEmpty()) {int[] cur queue.poll();int i cur[0], j cur[1];int steps dist[i][j];int maxRight Math.min(n - 1, j grid[i][j]);int maxDown Math.min(m - 1, i grid[i][j]);// 向右移动遍历行 i 中所有未访问的列 c (j1 .. maxRight)Integer c rows[i].ceiling(j 1);while (c ! null c maxRight) {dist[i][c] steps 1;if (i m - 1 c n - 1) return dist[i][c];queue.offer(new int[]{i, c});// 从行集合和列集合中删除该格子rows[i].remove(c);cols[c].remove(i);c rows[i].ceiling(j 1); // 继续查找下一个}// 向下移动遍历列 j 中所有未访问的行 r (i1 .. maxDown)Integer r cols[j].ceiling(i 1);while (r ! null r maxDown) {dist[r][j] steps 1;if (r m - 1 j n - 1) return dist[r][j];queue.offer(new int[]{r, j});cols[j].remove(r);rows[r].remove(j);r cols[j].ceiling(i 1);}}return dist[m - 1][n - 1];}}思路要点1. BFS 层次遍历每次移动代价为 1访问一个新格子BFS 能保证首次到达终点时步数最少。2. TreeSet 优化查找· rows[i] 存储第 i 行尚未访问的列索引。· cols[j] 存储第 j 列尚未访问的行索引。· 当从 (i, j) 向右最多走 grid[i][j] 步时只需从 rows[i] 中查找区间 (j, jgrid[i][j]] 内的所有列每个格子只被处理一次避免 O(n) 遍历。3. 删除已访问格子当一个格子被访问后立即从 rows 和 cols 中删除确保以后不再重复考虑。4. 提前返回一旦到达 (m-1, n-1) 立即返回步数无需继续 BFS。复杂度分析· 时间复杂度O(mn log(mn))。每个格子最多入队一次每次从 TreeSet 中查找和删除的操作均为 O(log n)行或 O(log m)列。· 空间复杂度O(mn)。存储距离数组、行/列 TreeSet 以及 BFS 队列。