417. Pacific Atlantic Water Flow

Leetcode link

题目简介

题目给我们一个二维数组 heights 表示一个岛屿，其中每个元素代表岛屿各个位置的高度

该岛屿的北面与西面被太平洋包围；东面与南面被大西洋包围

题目要求下在哪些岛屿的位置的雨水可以同时流到太平洋与大西洋

雨水能从 A 流到 B 只有可能是 A 的高度大于等于 B 的高度

题目要我们返回所有符合条件的坐标的集合

解题思路

这题我们可以从水流入大海之前的最后一个位置开始，一点一点的往回找到水流过的地方

具体来说，我们可以从岛屿的四条与大海接壤的边开始，对边上的格子依次做深度优先遍历 dfs

dfs 的终止条件就是当前格子被搜寻过了，或者当前格子比上一个格子低（也就是水无法从当前格子流向上一个格子）

但是由于我们大海有两个，所以我们判断当前格子有没有被搜寻过需要区分是被流进太平洋的水流过，还是被流进大西洋的水流过

所以我们不能用一个简单的 true/false 来判断，我们可以用：

• 1 代表大西洋
• 2 代表太平洋

这样一来有两个好处：

1. 判断被哪个洋流过只需要进行一个简单的比特位的与操作就可以了
2. 如果当前格子被流进两个洋的水都流过了，那么它就是 3，如果当前格子为 3 我们就可以将其加入答案之中了

Javascript

/**
 * @param {number[][]} heights
 * @return {number[][]}
 */
var pacificAtlantic = function (heights) {
    const res = []
    const width = heights.length
    const len = heights[0].length

    // we use 0 for not visited
    // 1 for visited by Atlantic ocean
    // 2 for visited by Pacific ocean
    const ATLANTIC = 1
    const PACIFIC = 2
    const visited = Array.from({length: width}, _ => new Array(len).fill(0))

    const dfs = (x, y, h, mark) => {
        if (visited[x][y] & mark || heights[x][y] < h) {
            return
        }
        visited[x][y] += mark
        if (visited[x][y] === 3) {
            res.push([x, y])
        }
        // search neighbor cells
        if (x > 0) dfs(x - 1, y, heights[x][y], mark)
        if (x < width - 1) dfs(x + 1, y, heights[x][y], mark)
        if (y > 0) dfs(x, y - 1, heights[x][y], mark)
        if (y < len - 1) dfs(x, y + 1, heights[x][y], mark)
    }

    for (let i = 0; i < width; i++) {
        dfs(i, 0, 0, PACIFIC)
        dfs(i, len - 1, 0, ATLANTIC)
    }

    for(let j = 0;j < len;j++) {
        dfs(0, j, 0, PACIFIC)
        dfs(width - 1, j, 0, ATLANTIC)
    }

    return res
};