778. 水位上升的泳池中游泳

用时：20min

首先能看出来是一个考察DFS的题目

var swimInWater = function(grid) {
  let row = grid.length;
  let col = grid[0].length; 
  var step = 0
  while(true) {
    for(let i = 0 ; i < row ; i ++) {
      for(let j = 0 ; j < col ; j ++){
        grid[i][j] --
      }
    }
    var visited = []
    for(let i = 0 ; i < row ; i ++) {
      let arr = []
      for(let j = 0 ; j < col ; j ++) {
        arr.push(false)
      }
      visited.push(arr)
    }
    var dfs = function (i,j) {
        if ( i< 0 || j < 0 || i >= row || j >= col) return false 
        if (visited[i][j]) {
          return false
        } else {
          visited[i][j] = true
        }
        if (grid[i][j] > 0) return false
        if (i === row - 1 && j === col - 1 && grid[i][j] <= 0) return true
        return dfs(i+1,j) || dfs(i-1,j) || dfs(i,j-1)|| dfs(i,j + 1)
    }
    step++
    if (dfs(0,0) === true) break  
    
  }
  return step
};

想到我们不必从 1 开始尝试，可以用二分法找到最左插入点

var swimInWater = function(grid) {
  let row = grid.length;
  let col = grid[0].length; 
  let right = -Infinity
  let left = Infinity
  for(let i = 0 ; i < row ; i ++) {
    for(let j = 0 ; j < col ; j ++ ){
      let num = grid[i][j]
      right = Math.max(right,num)
      left = Math.min(left,num)
    }
  }
  let mid = left + Math.floor( (right - left) / 2 )
  while(left <= right) {
    mid = left + Math.floor( (right - left) / 2 )
    var visited = []
    var new_grid = []
    for(let i = 0 ; i < row ; i ++) {
      let arr = []
      let _grid = []
      for(let j = 0 ; j < col ; j ++) {
        arr.push(false)
        _grid.push(grid[i][j] - mid)
      }
      visited.push(arr)
      new_grid.push(_grid)
    }

    var dfs = function (i,j) {
      if ( i < 0 || j < 0 || i >= row || j >= col) return false 
      if (visited[i][j]) {
        return false
      } else {
        visited[i][j] = true
      }
      if (new_grid[i][j] > 0) return false
      if (i === row - 1 && j === col - 1 && new_grid[i][j] <= 0) return true
      return dfs(i+1,j) || dfs(i-1,j) || dfs(i,j-1)|| dfs(i,j + 1)
    }
    if(dfs(0,0)) {
      // 找到了备胎，继续看能不能更小 
      right = mid - 1
    } else {
      left =  mid + 1
    }
  }
  return left
};