417. 太平洋大西洋水流问题

417. 太平洋大西洋水流问题

leetcode 链接

解法一：深度优先搜索

深度优先搜索，暴力解法，双重遍历矩阵，判断从当前坐标能不能找到两条可以到达太平洋和大西洋的路径。

需要注意的从当前坐标出发有上下左右四个方向，走过的就不用走了，所以需要记录本次循环中走过的坐标（roadListOfPacific 和 roadListOfAtlantic），如果判断走过则直接返回 false，别忘了每次循环开始要清空。

还有一点如果只是这样搜索，可能会超时，所以可以做一些缓存优化（canToPacific 和 canToAtlantic），循环中如果当前坐标可以达到太平洋或大西洋就记录下来，下次遍历到的时候就可以直接判断为 true，这是以空间换时间的做法。

/**
 * @param {number[][]} heights
 * @return {number[][]}
 */
function pacificAtlantic(heights) {
  const m = heights[0].length
  const n = heights.length
  const res = []
  const roadListOfPacific = [] // 单次循环路径记录列表
  const roadListOfAtlantic = [] // 单次循环路径记录列表
  const canToPacific = [] // 可以到达太平洋的矩阵点列表
  const canToAtlantic = [] // 可以到达大西洋的矩阵点列表
  const toLeftOrTop = (x, y) => {
    return x === 0 || y === 0 || canToPacific.includes(`${x},${y}`)
  }

  const toRightOrBottom = (x, y) => {
    return x === n - 1 || y === m - 1 || canToAtlantic.includes(`${x},${y}`)
  }

  const computePacific = (x, y) => {
    if (
      roadListOfPacific.includes(`${x},${y}`)
      || x < 0
      || x >= n
      || y < 0
      || y >= m
    ) {
      return false
    }
    roadListOfPacific.push(`${x},${y}`)
    if (toLeftOrTop(x, y))
      return true
    const cur = heights[x][y]
    return (
      (x > 0 && heights[x - 1][y] <= cur && computePacific(x - 1, y))
      || (y > 0 && heights[x][y - 1] <= cur && computePacific(x, y - 1))
      || (x < n - 1 && heights[x + 1][y] <= cur && computePacific(x + 1, y))
      || (y < m - 1 && heights[x][y + 1] <= cur && computePacific(x, y + 1))
    )
  }
  const computeAtlantic = (x, y) => {
    if (
      roadListOfAtlantic.includes(`${x},${y}`)
      || x < 0
      || x >= n
      || y < 0
      || y >= m
    ) {
      return false
    }
    roadListOfAtlantic.push(`${x},${y}`)
    if (toRightOrBottom(x, y))
      return true
    const cur = heights[x][y]
    return (
      (x < n - 1 && heights[x + 1][y] <= cur && computeAtlantic(x + 1, y))
      || (y < m - 1 && heights[x][y + 1] <= cur && computeAtlantic(x, y + 1))
      || (x > 0 && heights[x - 1][y] <= cur && computeAtlantic(x - 1, y))
      || (y > 0 && heights[x][y - 1] <= cur && computeAtlantic(x, y - 1))
    )
  }
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
      // 每次循环都清空记录
      roadListOfPacific.length = 0
      roadListOfAtlantic.length = 0
      if (computePacific(i, j)) {
        canToPacific.push(`${i},${j}`)
      }
      else {
        continue
      }
      if (computeAtlantic(i, j)) {
        canToAtlantic.push(`${i},${j}`)
      }
      else {
        continue
      }
      res.push([i, j])
    }
  }
  return res
}

解法二：水往高处流

与解法一思路相反，从边界开始搜索，把可以走到的坐标保存到两个数组（一个为太平洋的，一个为大西洋的），最后取交集就好。

/**
 * @param {number[][]} heights
 * @return {number[][]}
 */
function pacificAtlantic(heights) {
  const pacificList = []
  const atlanticList = []
  const res = []
  const m = heights[0].length
  const n = heights.length
  const pushList = (x, y, list) => {
    if (list.includes(`${x},${y}`))
      return
    list.push(`${x},${y}`)
    const cur = heights[x][y]
    if (x < n - 1 && heights[x + 1][y] >= cur) {
      pushList(x + 1, y, list)
    }
    if (x > 0 && heights[x - 1][y] >= cur) {
      pushList(x - 1, y, list)
    }
    if (y < m - 1 && heights[x][y + 1] >= cur) {
      pushList(x, y + 1, list)
    }
    if (y > 0 && heights[x][y - 1] >= cur) {
      pushList(x, y - 1, list)
    }
  }
  for (let i = 0; i < m; i++) {
    pushList(0, i, pacificList)
    pushList(n - 1, i, atlanticList)
  }
  for (let i = 0; i < n; i++) {
    pushList(i, 0, pacificList)
    pushList(i, m - 1, atlanticList)
  }
  for (let i = 0; i < pacificList.length; i++) {
    if (atlanticList.includes(pacificList[i])) {
      res.push(pacificList[i].split(','))
    }
  }
  return res
}