### 417. Pacific Atlantic Water Flow

Given an `m x n` matrix of non-negative integers representing the height of each unit cell in a continent, `the "Pacific ocean" touches the left and top edges of the matrix` and `the "Atlantic ocean" touches the right and bottom edges`.

Water can only flow in four directions (up, down, left, or right) `from a cell to another one with height equal or lower`.

Find the list of grid coordinates `where water can flow to both the Pacific and Atlantic ocean`.

Note:

• The order of returned grid coordinates does not matter.
• Both m and n are less than 150.

Example 1:

``````Given the following 5 x 5 matrix:

var test = [[1, 2, 2, 3, 5], [3, 2, 3, 4, 4], [2, 4, 5, 3, 1], [6, 7, 1, 4, 5], [5, 1, 1, 2, 4]]

Pacific ~   ~   ~   ~   ~
~  1   2   2   3  (5) *
~  3   2   3  (4) (4) *
~  2   4  (5)  3   1  *
~ (6) (7)  1   4   5  *
~ (5)  1   1   2   4  *
*   *   *   *   * Atlantic

Return:

[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (positions with parentheses in above matrix).``````

Example 2:

``````var test = [[3, 3, 3], [3, 1, 3], [0, 2, 4]]

Pacific ~   ~   ~
~  3   3   3  *
~  3   1   3  *
~  0   2   4  *
*   *   *  Atlantic``````

### Analyze

• 有效出发点:
• 存在到 Pacific 的路径;
• 存在到 Atlantic 的路径;
• 使用「染色算法」在比当前值小的方向递归找寻
``````/**
* @param {number[][]} matrix
* @return {number[][]}
*/
var pacificAtlantic = function(matrix) {
const result = []
for (let m = 0; m < matrix.length; m++) {
for (let n = 0; n < matrix[m].length; n++) {
const usedPacific = []
const usedAtlantic = []
if (iterator(matrix, m, n, usedPacific, 'pacific')
&& iterator(matrix, m, n, usedAtlantic, 'atlantic')) {
result.push([m, n])
}
}
}
return result
};

var directions = [[1, 0], [0, 1], [-1, 0], [0, -1]] // bottom、right、top、left

var iterator = function(matrix, m, n, used, tag) {
used.push(`\${m},\${n}`)

// achieve the board of matrix
if (tag === 'pacific' ? ifReachPacific(m, n) : ifReachAtlantic(matrix, m, n)) {
return true
}

for (let i = 0; i < directions.length; i++) {
if (!isValid(matrix, m + directions[i][0], n + directions[i][1], used)) continue
const newPoint = matrix[m + directions[i][0]][n + directions[i][1]]
if (newPoint > matrix[m][n]) {
continue
}
const nextIsValid = iterator(matrix, m + directions[i][0], n + directions[i][1], used, tag)
if (nextIsValid) {
return true
}
}
return false
}

// judge if is valid
var isValid = (matrix, m, n, used) => {
if (used.indexOf(`\${m},\${n}`) > -1 || !(matrix[m] && typeof matrix[m][n] === 'number')) return false
return true
}

var ifReachPacific = function(m, n) {
return m === 0 || n === 0
}

var ifReachAtlantic = function(matrix, m, n) {
return m === matrix.length - 1 || n === matrix[0].length - 1
}``````

130