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

/**
 * @param {number[][]} heights
 * @return {number[][]}
 */
var pacificAtlantic = function(heights) {
    if(!heights||!heights[0]){return []}
    // 这道题让咱从高点往低点流 咱们可以逆向思维让大西洋和太平洋的水逆向流动到高点
    var r = heights.length
    var c = heights[0].length
    // flow1存太平洋可以逆向流动的所有点 flow1存大西洋可以逆向流动的所有点
    const flow1 = Array.from({ length: r }, () => new Array(c).fill(false));
    const flow2 = Array.from({ length: r }, () => new Array(c).fill(false));


    // 运用图的深度优先遍历来遍历从大西洋和太平洋中可以逆向流动（从小到大）的点
    function dfs(m,n,flow){
        flow[m][n] = true
        let arr = [[m-1,n],[m+1,n],[m,n-1],[m,n+1]]
        arr.forEach(([m1,n1])=>{
            if(
                // m1 n1在矩阵内
                m1>=0 && m1<r &&
                n1>=0 && n1<c &&
                // 这个点要比上一个点高
                heights[m1][n1] >= heights[m][n] &&
                // 防止死循环
                !flow[m1][n1]
            ){
                dfs(m1,n1,flow)
            }
        })
    }
    
    // 对太平洋和大西洋海岸线的所有点进行dfs
    for(let i =0;i < r;i++){
        dfs(i,0,flow1)
        dfs(i,c-1,flow2)
    }
    for(let i =0;i<c;i++){
        dfs(0,i,flow1)
        dfs(r-1,i,flow2)
    }
    var res = []
    for(let i =0;i<r;i++){
        for(let j =0;j<c;j++){
            if(flow1[i][j]&&flow2[i][j]){
                res.push([i,j])
            }
        }
    }
    return res

};

最后

以上就是纯情薯片为你收集整理的Leecode 417. 太平洋大西洋水流问题的全部内容，希望文章能够帮你解决Leecode 417. 太平洋大西洋水流问题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。