【每日一题】- 2019-08-13 - 417. 太平洋大西洋水流问题 about leetcode HOT 5 CLOSED

/**
 * @param {number[][]} matrix
 * @return {number[][]}
 * 
 * 逆向模式来做
 * 先统计能从太平洋反流回来的坐标
 * 再统计能从大西洋反流回来的坐标
 * 
 * 最后将两个集合中都为true的坐标输出
 */
var pacificAtlantic = function (matrix) {
    if (matrix.length == 0) return [];
    var m = matrix.length,
        n = matrix[0].length;

    var dpt = Array.from({ // 记录能流入太平洋的位置
        length: m
    }, () => new Array(n).fill(false));
    var dpd = Array.from({ // 记录能流入大西洋的位置
        length: m
    }, () => new Array(n).fill(false));

    // 从太平洋的起点搜索，也就是最上边一排的元素位置和左边竖排元素的位置
    for (var i = 0; i < matrix.length; i++) {
        for (var j = 0, len = i == 0 ? n : 1; j < len; j++) {
            temp(i, j, -1, dpt);
        }
    }

    // 大西洋
    for (var i = 0; i < matrix.length; i++) {
        for (var j = n - 1, len = i == m - 1 ? 0 : n - 1; j >= len; j--) {
            temp(i, j, -1, dpd);
        }
    }

    var rel = [];
    for (var i = 0; i < dpt.length; i++) {
        for (var j = 0; j < dpt[i].length; j++) {
            if (dpt[i][j] && dpt[i][j] == dpd[i][j]) {
                rel.push([i, j])
            }
        }
    }

    return rel;

    function temp(x, y, preNumber, mem) {
        var nowNum = matrix[x] && matrix[x][y];
        if (nowNum == null) return; // 如果跨越边界，则返回
        if (mem[x][y]) { // 如果此位置已经可以流入大西洋或者太平洋，则直接返回
            return mem[x][y];
        }
        if (nowNum >= preNumber) { // 如果此位置比上一个位置的元素值大，则符合条件，然后再搜索基于它的上下左右四个位置
            mem[x][y] = true;
            temp(x - 1, y, nowNum, mem);
            temp(x + 1, y, nowNum, mem);
            temp(x, y - 1, nowNum, mem);
            temp(x, y + 1, nowNum, mem);
        }
    }
};

function dfs(i, j, height, m, matrix, rows, cols) {
  if (i >= rows || i < 0) return;
  if (j >= cols || j < 0) return;

  if (matrix[i][j] < height) return;

  if (m[i][j] === true) return;

  m[i][j] = true;

  dfs(i + 1, j, matrix[i][j], m, matrix, rows, cols);
  dfs(i - 1, j, matrix[i][j], m, matrix, rows, cols);
  dfs(i, j + 1, matrix[i][j], m, matrix, rows, cols);
  dfs(i, j - 1, matrix[i][j], m, matrix, rows, cols);
}
/**
 * @param {number[][]} matrix
 * @return {number[][]}
 */
var pacificAtlantic = function(matrix) {
  const rows = matrix.length;
  if (rows === 0) return [];
  const cols = matrix[0].length;
  const pacific = Array.from({ length: rows }, () => Array(cols).fill(false));
  const atlantic = Array.from({ length: rows }, () => Array(cols).fill(false));
  const res = [];

  for (let i = 0; i < rows; i++) {
    dfs(i, 0, 0, pacific, matrix, rows, cols);
    dfs(i, cols - 1, 0, atlantic, matrix, rows, cols);
  }

  for (let i = 0; i < cols; i++) {
    dfs(0, i, 0, pacific, matrix, rows, cols);
    dfs(rows - 1, i, 0, atlantic, matrix, rows, cols);
  }

  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      if (pacific[i][j] === true && atlantic[i][j] === true) res.push([i, j]);
    }
  }

  return res;
};