3回答

liuyubobobo

2022-05-10

已采纳

可以写成一个 dfs 函数，只要这个函数返回两个值即可。如果你所使用的语言不支持返回多个值，就包装成一个类或者用数组即可。

但是，关键是，这个方式应该是超时的。因为对 n^2 个点做 n^2 次 dfs，每次时间复杂度都是 O(n^2) 的，总时间复杂度是 O(n^4) 的。对于这个问题，n = 200，n^4 达到 1e9 这个级别，道理上是超时的。

你的这个 js 代码是可以 ac 的吗？如果可以的话，请贴一版可提交的代码，我测试一下？谢谢：）

0

1

甲骨文_0001

老师，代码回复你了，你看下哈，然后leetcode上可以AC, 时间是5208 ms, 内存消耗是54.5 MB :)

2022-05-10

共1条回复

liuyubobobo

2022-05-10

明白了，那说明力扣 js 给的时限的宽松是过了的，导致 C++ 无法过的算法 js 可以过。这是个漏洞，看来以后里扣的比赛 C++ TLE 的问题可以考虑搞 js 试一下：）

以下是我基于你的代码修改的单个 dfs 的算法。在返回值上我使用了位压缩。返回值的第 0 位是 1 表示能到太平洋，第 1 位为 1  表示能到大西洋。所以返回值为 3（二进制的 11）表示两个地方都能到。

const d = [[1, 0], [-1, 0], [0, 1], [0, -1]];

var pacificAtlantic = function(heights) {
    let matrix = heights;
    let res=[]; // 结果
    const R = matrix.length, C = matrix[0].length; // R行C列
    let mark = Array(R).fill([]).map(_=>Array(C).fill(-1));
    for( let r = 0; r < R; r ++ ){
        for( let c = 0; c < C; c ++ ){
            let a = dfs(matrix, mark, r, c);
            if(a == 3) res.push([r, c]); // 说明r行c列能到达两处海洋
            mark = Array(R).fill([]).map(_=>Array(C).fill(-1));
        } // end for c
    } // end for r
    return res;
};
 
function dfs( matrix, mark, r, c ){
    const R = matrix.length, C = matrix[0].length;
    let res = 0;
    if( r == 0 || c == 0 ){ // 能到太平洋
        res |= 1;
    }
    if( r == R-1 || c == C-1 ){ // 能到大西洋
        res |= 2;
    }
    mark[r][c] =res;
    
    for( let i = 0; i < 4; i ++ ){
        let newR = r+d[i][0], newC = c + d[i][1];
        if( inArea(matrix, newR, newC) && mark[newR][newC] == -1 && matrix[r][c] >= matrix[newR][newC] ){
            res |= dfs( matrix, mark, newR, newC );
        }
    } // end for i
    return res;
}
 
function inArea( matrix, r, c ){
    const R = matrix.length, C = matrix[0].length;
    return r >= 0 && r < R && c >= 0 && c < C;
}

继续加油！：）

1

0

甲骨文_0001

提问者

2022-05-10

const d = [[1, 0], [-1, 0], [0, 1], [0, -1]];

/**
 * @param {number[][]} heights
 * @return {number[][]}
 */
var pacificAtlantic = function(heights) {
    let matrix = heights;
    let res=[]; // 结果
    const R = matrix.length, C = matrix[0].length; // R行C列
    let pacific = Array(R).fill([]).map(_=>Array(C).fill(false)); // visited数组,标记是否访问过
    let atlantic = Array(R).fill([]).map(_=>Array(C).fill(false));

    for( let r = 0; r < R; r ++ ){
        for( let c = 0; c < C; c ++ ){
            // 看能否到太平洋
            let canPacific = dfsPacific(matrix, pacific, r, c);
            // 再看能否到大西洋
            let canAtlantic = dfsAtlantic(matrix, atlantic, r, c);

            if( canPacific && canAtlantic ){
                res.push([r, c]); // 说明r行c列能到达两处海洋
            }

            // 然后将两个visited数组重置为false
            pacific = Array(R).fill([]).map(_=>Array(C).fill(false));
            atlantic = Array(R).fill([]).map(_=>Array(C).fill(false));
        } // end for c
    } // end for r
    return res;
};

function dfsPacific( matrix, visited, r, c ){
    const R = matrix.length, C = matrix[0].length;
    if( r == 0 || c == 0 ){ // 能到太平洋
        return true;
    }
    visited[r][c] = true;
    for( let i = 0; i < 4; i ++ ){
        let newR = r+d[i][0], newC = c + d[i][1];
        if( inArea(matrix, newR, newC) && !visited[newR][newC] && matrix[r][c] >= matrix[newR][newC] ){
            if( dfsPacific( matrix, visited, newR, newC ) ){
                return true;
            }
        }
    } // end for i
    return false;
}

function dfsAtlantic( matrix, visited, r, c ){
    const R = matrix.length, C = matrix[0].length;
    if( r == R-1 || c == C-1 ){ // 能到大西洋
        return true;
    }
    visited[r][c] = true;
    for( let i = 0; i < 4; i ++ ){
        let newR = r+d[i][0], newC = c + d[i][1];
        if( inArea(matrix, newR, newC) && !visited[newR][newC] && matrix[r][c] >= matrix[newR][newC] ){
            if( dfsAtlantic( matrix, visited, newR, newC ) ){
                return true;
            }
        }
    } // end for i
    return false;
}

function inArea( matrix, r, c ){
    const R = matrix.length, C = matrix[0].length;
    return r >= 0 && r < R && c >= 0 && c < C;
}

0

0