Pacific Atlantic current problems

describe

Given a matrix of m x n nonnegative integers to represent the heights of cells on a continent. The Pacific Ocean is on the left and upper boundary of the continents, while the Atlantic Ocean is on the right and lower boundary of the continents.

It is stipulated that water can only flow in four directions: up, down, left and right, and can only flow from high to low or at the same height.

Find the coordinates of the land units where water flows to both the Pacific and Atlantic oceans.

Tip:

The order of the output coordinates doesn’t matter m and n are both less than 150

The sample

Given the following 5x5 matrix: Pacific ~ ~ ~ ~ ~ ~ 1 2 3 (5) * 2 ~ 3 3 (4) (4) * 2 ~ 4 (5) 3 1 * 2 ~ (6) (7) ~ (5) 1, 4, 5 * 1 1 2 4 * * * * * * to: [[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (pictured above with parentheses unit).Copy the code

Answer key

Although the title is satisfied downstream to reach the location of two oceans, if we search all locations, it would be “very complicated” without pruning.

So we can think of it the other way around, starting with two oceans and moving up, and then we only need to search the four sides of the rectangle. Once the search is complete, you simply “run through the matrix” and the position that satisfies the condition is the position that both oceans can reach upwardly.

In a nutshell.

The water goes up, from the Pacific and the Atlantic, records the highs, and finds the overlap.

coding

/ * * *@param {number[][]} heights
 * @return {number[][]}* /
 const direction = [-1.0.1.0, -1];
 / / the main function
var pacificAtlantic = function(heights) {
   if(! heights || ! heights.length || ! heights[0].length) return [];
    let ans = [], m = heights.length, n = heights[0].length;  
    const P = Array.from({length: m}, () = > Array(n).fill(0));
    const A = Array.from({length: m}, () = > Array(n).fill(0));
    for(let i = 0; i < m; i++) {
        dfs(heights, P, i, 0);
        dfs(heights, A, i, n - 1);
    }  
    for(let i = 0; i < n; i++) {
        dfs(heights, P, 0, i);
        dfs(heights, A, m - 1, i);
    }
    for(let i = 0; i < m; i ++) {
        for(let j = 0; j < n; j++) {
            if(P[i][j] && A[i][j]) { ans.push([i, j]); }}};return ans;

};
// Auxiliary functions
const dfs = function(matrix, can_reach, r, c) {
    if(can_reach[r][c]) return;
    can_reach[r][c] = true;
    let x, y;
    for(let i = 0; i < 4; i++) {
        x = r + direction[i], y = c + direction[i+1];
        if(x >= 0 && x < matrix.length && y >= 0 && y < matrix[0].length && matrix[r][c] <= matrix[x][y]) { dfs(matrix, can_reach, x, y); }}}Copy the code