417、太平洋大西洋水流问题 | 图-JS

本文主要是介绍417、太平洋大西洋水流问题 | 图-JS，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

给定一个 m x n 的非负整数矩阵来表示一片大陆上各个单元格的高度。“太平洋”处于大陆的左边界和上边界，而“大西洋”处于大陆的右边界和下边界。

规定水流只能按照上、下、左、右四个方向流动，且只能从高到低或者在同等高度上流动。

请找出那些水流既可以流动到“太平洋”，又能流动到“大西洋”的陆地单元的坐标。

提示：

1.     输出坐标的顺序不重要
2.     m 和 n 都小于150

示例：

给定下面的 5x5 矩阵:

  太平洋 ~   ~   ~   ~   ~
       ~  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]] (上图中带括号的单元)

 1 /**
 2  * @param {number[][]} heights
 3  * @return {number[][]}
 4  */
 5 var pacificAtlantic = function(matrix) {
 6     //排查矩阵为空的情况,或者不是一个二维矩阵
 7     if(!matrix || !matrix[0]) return [];
 8     const m = matrix.length;
 9     const n = matrix[0].length;
10     //新建两个矩阵来记录
11     const flow1 = Array.from({ length: m} , () => new Array(n).fill(false));
12     const flow2 = Array.from({ length: m} , () => new Array(n).fill(false));
13     
14     const dfs = (r , c , flow) => {
15         flow[r][c] = true;
16         [[r-1,c],[r+1,c],[r,c-1],[r,c+1]].forEach(([nr,nc]) => {
17             if(
18                 //保证要在矩阵中
19                 nr >= 0 && nr < m &&
20                 nc >= 0 && nc < n &&
21                 //防止死循环
22                 !flow[nr][nc] &&
23                 //保证逆流而上
24                 matrix[nr][nc] >= matrix[r][c]
25             ){
26                 dfs(nr, nc, flow);
27             }
28         })
29     }
30 
31     // 沿着海岸线逆流而上
32     for(let r = 0; r < m ; r++){
33         dfs(r,0,flow1);
34         dfs(r,n-1,flow2);
35     }
36     for(let c = 0; c< n;c++){
37         dfs(0, c , flow1);
38         dfs(m-1, c , flow2);
39     }
40     // 收集能流到两个大洋里的坐标
41     const res = [];
42     for(let r = 0; r<m ; r++) {
43         for(let c = 0; c<n ; c++){
44             if(flow1[r][c] && flow2[r][c]){
45                 res.push([r,c]);
46             }
47         }
48     }
49     return res;
50 };

这篇关于417、太平洋大西洋水流问题 | 图-JS的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！