核心思想
比较直观的想法就是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});//移出Setiterator.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});//移出Setiterator.remove();R[row].remove(j);}}}return f[n-1][m-1];}