[数据结构与算法]Leetcode刷题(第417题)——太平洋大西洋水流问题

一、题目

二、示例

输入: heights = [[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]]
输出: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]

输入: heights = [[2,1],[1,2]]
输出: [[0,0],[0,1],[1,0],[1,1]]

三、思路
1、这题采用图的深度优先遍历
2、创建两个二维矩阵，其中的值都设置为false
3、分别从大西洋和太平洋海岸线起步，经过之处节点的值设置为true
4、最后再将两个图进行比对，拿出两张图的节点都是true的节点并保存
5、最后返回
四、代码

/**
 * @param {number[][]} heights
 * @return {number[][]}
 */
var pacificAtlantic = function(heights) {
    let row = heights.length
    let col = heights[0].length
    let flow1 = new Array(row).fill(0).map(item => new Array(col).fill(false))
    let flow2 = new Array(row).fill(0).map(item => new Array(col).fill(false))
    const rec = (x, y, flow) => {
        if(x < 0 || x >= row || y < 0 || y >= col) return
        flow[x][y] = true
        ;[[x, y + 1],[x + 1, y], [x, y - 1], [x -1, y]].forEach(([xp, yp]) => {
            if(heights[xp][yp] >= heights[x][y]) {
                rec(x, y, flow)
            }
        })
    }
    for(let i = 0; i < row; i++) {
        rec(i, 0, flow1)
        rec(i, col - 1, flow2)
    }
    for(let j = 0; j < col; j++) {
        rec(0, j, flow1)
        rec(row - 1, j, flow2)
    }
    console.log(flow1)
    console.log(flow2)
};

五、总结