题目

题解

水只会往两个方向流动，一个是低处，一个是水平处。不同与其他深度遍历，其他的深度遍历都是从数组挨个开始的。而这次需要从数组的四条边往里面深度优先搜索。这是为什么？小岛里的水想要流向大海，那吗小岛内就需要有个高点，这样水才能向下流，找这个点很难，但是它最后的出水口肯定在岛的四周，也就是数组的四条边。我们假设从岛的四周一点点探寻，寻找能所有能流进太平洋与能流进大西洋的路线，当路线上点重合的时候就是既能流进太平洋又能流进大西洋的路线，这也是我们要找的答案，就像是顺藤摸瓜，从岛的四周开始往岛内部探索
，

/**
 * @param {number[][]} heights
 * @return {number[][]}
 */
var pacificAtlantic = function (heights) {
  // 行的宽度 
  const rLen = heights.length;
  // 列的宽度   
  const cLen = heights[0].length;
  // 矩阵，与给定的数组相对应，当某一项为true说明能流进太平洋
  let canReachP = new Array(rLen);
  // 矩阵，与给定的数组相对应，当某一项为true说明能流进大西洋
  let canReachA = new Array(rLen);
  // 为矩阵添加初始值， 每一项的初始值都是false
  for(let r = 0; r < rLen; r++) {
      canReachA[r] = new Array(cLen).fill(false);
      canReachP[r] = new Array(cLen).fill(false);
  }
  // 存放结果的数组
  const result = [];
  // dfs
  const dfs = (canReachArr, row, col) => {
    // 水流的方向
  const direction = [-1, 0, 1, 0, -1];
    // 当为true 说明水流经过这里
  if(canReachArr[row][col]) {
    return;
  }
  // 将对应的矩阵的对应点改为true 说明水流过这里
  canReachArr[row][col] = true;
  // 水流的下一个位置
  for(let i = 0; i < 4; i++) {
    let x = row + direction[i];
    let y = col + direction[i + 1];
    if(x >= 0 && x < rLen && y >= 0 && y < cLen && heights[row][col] <= heights[x][y]) {
      dfs(canReachArr, x, y)
    }
  }
}
  // 水想从小岛流出来，那吗岸边会是小岛最低处
  // 从小岛最左面和最右面开始寻找上游的终点
  for(let r = 0; r < rLen; r++) {
    dfs(canReachP, r, 0);
    dfs(canReachA, r, cLen - 1);
  }
  // 从小岛最下面和最上面寻找上游的的终点
  for(let c = 0; c < cLen ; c++) {
    dfs(canReachA, rLen - 1, c);
    dfs(canReachP, 0, c);
  }
  // 找到那些流向太平洋与大西洋的水流的共同点
  for(let r = 0; r < rLen; r++) {
    for (let c = 0; c < cLen; c++) {
      if (canReachA[r][c] && canReachP[r][c]) {
        result.push([r, c]);
      }
    }
  }
  return result
};