DeepSeek LeetCode 2617. 网格图中最少访问的格子数 Java实现
以下是 LeetCode 2617「网格图中最少访问的格子数」的 Java 实现，采用 BFS + TreeSet 优化，保证每个格子只被访问一次，时间复杂度 O(mn log(m+n))。
```java
class 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;
// 每一行未访问的列索引
TreeSet<Integer>[] rows = new TreeSet[m];
// 每一列未访问的行索引
TreeSet<Integer>[] 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);
}
}
Queue<int[]> 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 (j+1 .. 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 (i+1 .. 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, j+grid[i][j]] 内的所有列，每个格子只被处理一次，避免 O(n) 遍历。
3. 删除已访问格子
当一个格子被访问后，立即从 rows 和 cols 中删除，确保以后不再重复考虑。
4. 提前返回
一旦到达 (m-1, n-1) 立即返回步数，无需继续 BFS。
复杂度分析
· 时间复杂度：O(mn log(m+n))。每个格子最多入队一次，每次从 TreeSet 中查找和删除的操作均为 O(log n)（行）或 O(log m)（列）。
· 空间复杂度：O(mn)。存储距离数组、行/列 TreeSet 以及 BFS 队列。