[数据结构与算法]太平洋大西洋水流问题（图）

落日映苍穹つ 2022-12-12 02:11 82阅读 0赞

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

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

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

提示：

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

示例：

给定下面的 5x5 矩阵:  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTQwMjE5_size_16_color_FFFFFF_t_70_pic_center]

返回:

[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (上图中带括号的单元).

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/pacific-atlantic-water-flow  
解题：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTQwMjE5_size_16_color_FFFFFF_t_70_pic_center 1]

var matrix = [
          [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]
        ]
    
        var pacificAtlantic = function (matrix) { 
          if (!matrix || !matrix[0]) { 
            return []
          }
          const m = matrix.length; // 矩阵行数
          const n = matrix[0].length // 矩阵列数
    
          // 下面两行代码表示创建一个m行n列全部填充为false的二维数组
          const flow1 = Array.from({ 
            length: m
          }, () => new Array(n).fill(false)) // 用于记录能流到太平洋的单元
          const flow2 = Array.from({ 
            length: m
          }, () => new Array(n).fill(false)) // 用于记录能流到大西洋的单元
    
          const dfs = (r, c, flow) => {  // 参数为行 列 太平洋/大西洋二维数组
            flow[r][c] = true
            ;[ // 注意：在以 “(“、”[“ 、”/“、”+”、”-“ 开头的语句前请加分号,防止运行为true[]
              [r - 1, c],
              [r + 1, c],
              [r, c - 1],
              [r, c + 1]
            ].forEach(([nr, nc]) => {  // nr,nc代表下一个行/列
              if (
                // 保证下一个节点在矩阵中
                nr >= 0 && nr < m && nc >= 0 && nc < n &&
                // 防止死循环
                !flow[nr][nc] &&
                // 保证逆流而上
                matrix[nr][nc] >= matrix[r][c]
              ) { 
                dfs(nr, nc, flow)
              }
            })
          }
    
          // 沿着海岸线逆流而上
          for (let r = 0; r < m; r++) { 
            dfs(r, 0, flow1)
            dfs(r, n - 1, flow2)
          }
          for (let c = 0; c < n; c++) { 
            dfs(0, c, flow1)
            dfs(m - 1, c, flow2)
          }
    
          // 收集能流到两个大洋中的坐标
          const res = []
          for (let r = 0; r < m; r++) { 
            for (let c = 0; c < n; c++) { 
              if (flow1[r][c] && flow2[r][c]) { 
                res.push([r, c])
    
              }
            }
          }
          return res
        }
        console.log(pacificAtlantic(matrix))

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTQwMjE5_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/8a71d1e72e994d01b7d341f101ee19be.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTQwMjE5_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/f6f72f6fe5a24c31ba7f76e4258f0e65.png

发表评论取消回复

表情：

评论列表（有 0 条评论，82人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode | 0417. Pacific Atlantic Water Flow太平洋大西洋水流问题【Python】

> LeetCode 0417. Pacific Atlantic Water Flow太平洋大西洋水流问题【Medium】【Python】【DFS】 Problem

谁践踏了优雅/ 2023年07月10日 05:19/ 0 赞/ 4 阅读

相关算法与数据结构之图

重要概念 1. 在数据结构中，线性结构，树形结构和图形结构数据元素之间分别存着一对一，一对多，多对多的联系。 2. n个顶点的连通图至少有n-1条边。 3. 有向图G

水深无声/ 2022年12月17日 04:25/ 0 赞/ 183 阅读

相关 LeetCode 417. 太平洋大西洋水流问题 JAVA dfs

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

小咪咪/ 2022年12月14日 00:34/ 0 赞/ 92 阅读

相关 [数据结构与算法]太平洋大西洋水流问题（图）

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

落日映苍穹つ/ 2022年12月12日 02:11/ 0 赞/ 83 阅读

相关【数据结构与算法】图

一：如何理解“图” 1，图和树一样都是非线性表数据结构，和树不同的是图是一种更加复杂的非线性表结构 2，树中的元素称之为节点，图中的元素则称之为顶点。 3，顶点可以

港控/mmm°/ 2022年11月30日 04:20/ 0 赞/ 170 阅读

相关 leetcode 417. Pacific Atlantic Water Flow | 417. 太平洋大西洋水流问题（DFS，经典“感染”思路）

题目 [https://leetcode.com/problems/pacific-atlantic-water-flow/][https_leetcode.com_pr

阳光穿透心脏的1/2处/ 2022年09月03日 01:22/ 0 赞/ 105 阅读

相关数据结构与算法之图

图跟树一样，也是非线性结构，咋看起来有点复杂，其实它很简单。树具有层次关系，上层元素可以与下一个多个元素连接，但是只能和上层的一个元素连接。在图结构中，节点间的连接是任意的，任

梦里梦外;/ 2022年06月07日 02:23/ 0 赞/ 186 阅读

相关数据结构与算法---5（图）

图在线性表中，数据元素之间是被串起来的，仅有线性关系，每个数据元素都只有一个直接前驱和直接后继；在树形结构中，数据元素之间有着明显的层次结构，但是每一个元素肯定值只有一

「爱情、让人受尽委屈。」/ 2022年02月26日 06:28/ 0 赞/ 372 阅读

相关 C++数据结构与算法（图）

> 回顾：线性表中，每个元素只有一个直接前驱和直接后继，在树形结构中，数据之间是层次关系，并且每一层上的数据元素可能和下一层中多个元素相关，但只能和上一层中一个元素相关。但这都

谁借莪１个温暖的怀抱￠/ 2021年10月31日 16:30/ 0 赞/ 397 阅读

相关数据结构与算法之图

图基本概念无向图和有向图 ![70][] 前一个不带箭头的就是无向图，后一个带尖头的就是有向图子图如果图G中包含G1，那么G1就是G的

桃扇骨/ 2021年06月11日 15:11/ 0 赞/ 547 阅读