核心思想
比较直观的想法就是BFS,但是每次遍历能走的点(右走,下走)会超时
考虑用两个set数组,
TreeSet<Integer>[] R = new TreeSet[n]; TreeSet<Integer>[] C = new TreeSet[m];
R[i]表示第i行还剩下哪些列col没去过,那么遍历就变为了二分查找第一个比当前j大的col
当col > j + grid[i][j]
时break
TODO:iterator
public int minimumVisitedCells(int[][] grid) {
// n 行 m 列
int n = grid.length, m = grid[0].length;
//存储步数
int[][] f = new int[n][m];
// 使用双重循环来填充二维数组
for (int i = 0; i < n; i++) {
Arrays.fill(f[i], -1);
}
TreeSet<Integer>[] R = new TreeSet[n];
TreeSet<Integer>[] C = new TreeSet[m];
for(int i = 0; i < n; i++)
R[i] = new TreeSet<Integer>();
for(int j = 0; j < m; j++)
C[j] = new TreeSet<Integer>();
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(i + j > 0){
R[i].add(j);
C[j].add(i);
}
}
}
Queue<int[]> q = new ArrayDeque<>();
q.offer(new int[]{0, 0});
f[0][0] = 1;
while(!q.isEmpty()){
int[] tp = q.poll();
int i = tp[0], j = tp[1];
// 向右走 去R中找
// 第一个大于j的数
Integer ceil = R[i].ceiling(j);
if(ceil != null){
//最远距离
int maxiCol = j + grid[i][j];
Iterator<Integer> iterator = R[i].tailSet(ceil).iterator();
while(iterator.hasNext()){
int col = iterator.next();
if (col > maxiCol)
break;
//记录步数
f[i][col] = f[i][j] + 1;
//推入队列
q.offer(new int[]{i, col});
//移出Set
iterator.remove();
C[col].remove(i);
}
}
// 向下走 去C中
// 第一个大于i的数
ceil = C[j].ceiling(i);
if(ceil != null){
//最远距离
int maxiRow = i + grid[i][j];
Iterator<Integer> iterator = C[j].tailSet(ceil).iterator();
while(iterator.hasNext()){
int row = iterator.next();
if(row > maxiRow)
break;
//记录步数
f[row][j] = f[i][j] + 1;
//推入队列
q.offer(new int[]{row, j});
//移出Set
iterator.remove();
R[row].remove(j);
}
}
}
return f[n-1][m-1];
}
标签:2617,格子,iterator,int,网格,ceil,new,col,TreeSet
From: https://www.cnblogs.com/ganyq/p/18109113