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

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

leetcode 链接

解法一：深度优先搜索

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

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

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

/**
 * @param {number[][]} heights
 * @return {number[][]}
 */
var pacificAtlantic = function (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[][]}
 */
var pacificAtlantic = function (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;
};