1. 题目描述

https://leetcode-cn.com/problems/pacific-atlantic-water-flow/
有一个 m × n 的矩形岛屿，与 太平洋 和 大西洋 相邻。 “太平洋” 处于大陆的左边界和上边界，而 “大西洋” 处于大陆的右边界和下边界。
这个岛被分割成一个由若干方形单元格组成的网格。给定一个 m x n 的整数矩阵 heights ， 417. 太平洋大西洋水流问题 - 图1 表示坐标 417. 太平洋大西洋水流问题 - 图2#card=math&code=%28r%2C%20c%29&id=o4Cyr) 上单元格 高于海平面的高度 。
岛上雨水较多，如果相邻单元格的高度 小于或等于 当前单元格的高度，雨水可以直接向北、南、东、西流向相邻单元格。水可以从海洋附近的任何单元格流入海洋。
返回 网格坐标 result 的 2D列表 ，其中 417. 太平洋大西洋水流问题 - 图3 表示雨水可以从单元格 417. 太平洋大西洋水流问题 - 图4#card=math&code=%28r_i%2C%20c_i%29&id=EUIwD) 流向 太平洋和大西洋 。

示例 1：
417. 太平洋大西洋水流问题 - 图5
输入: heights = [[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]]

示例 2：
输入: heights = [[2,1],[1,2]]
输出: [[0,0],[0,1],[1,0],[1,1]]

提示：
417. 太平洋大西洋水流问题 - 图6
417. 太平洋大西洋水流问题 - 图7
417. 太平洋大西洋水流问题 - 图8
417. 太平洋大西洋水流问题 - 图9

2. 题解

2022-04-27 AC, 深搜/广搜都可以
目的是构造出两个答案矩阵 res_1和 res_2，res_k[i][j] = 1 代表格子 (i, j) 能够流向海域，起始从4边开始DFS，所有能够进入队列的格子均能够与海域联通。
最后统计所有满足 res_1[i][j] = res_2[i][j] = 1 的格子即是答案。

  1. <?php
  2. /**
  3.  * Created by PhpStorm
  4.  * User: jtahstu
  5.  * Time: 2022/4/27 22:50
  6.  * Des: 417. 太平洋大西洋水流问题
  7.  *      https://leetcode-cn.com/problems/pacific-atlantic-water-flow/
  8.  *      有一个 m × n 的矩形岛屿，与 太平洋 和 大西洋 相邻。 “太平洋” 处于大陆的左边界和上边界，而 “大西洋” 处于大陆的右边界和下边界。
  9.  * 这个岛被分割成一个由若干方形单元格组成的网格。给定一个 m x n 的整数矩阵 heights ， heights[r][c] 表示坐标 (r, c) 上单元格 高于海平面的高度 。
  10.  * 岛上雨水较多，如果相邻单元格的高度 小于或等于 当前单元格的高度，雨水可以直接向北、南、东、西流向相邻单元格。水可以从海洋附近的任何单元格流入海洋。
  11.  * 返回网格坐标 result 的 2D 列表 ，其中 result[i] = [ri, ci] 表示雨水从单元格 (ri, ci) 流动 既可流向太平洋也可流向大西洋 。
  12.  */
  14. class Solution
  15. {
  16.     /**
  17.      * @param Integer[][] $heights
  18.      * @return Integer[][]
  19.      */
  20.     function pacificAtlantic($heights)
  21.     {
  22.         $this->heights = $heights;
  23.         $this->x = count($heights[0]); //长
  24.         $this->y = count($heights); //宽
  25.         $ans1 = [];  //左/上结果集
  26.         $ans2 = [];  //右/下结果集
  27.         for ($i = 0; $i < $this->y; $i++) {
  28.             $this->dfs($i, 0, $ans1); //左边
  29.             $this->dfs($i, $this->x - 1, $ans2);  //右边
  30.         }
  31.         for ($j = 0; $j < $this->x; $j++) {
  32.             $this->dfs(0, $j, $ans1);  //上边
  33.             $this->dfs($this->y - 1, $j, $ans2);  //下边
  34.         }
  35.         //交集即为两边都能流出的结果
  36.         $ans = [];
  37.         for ($i = 0; $i < $this->y; $i++) { //这里先y后x
  38.             for ($j = 0; $j < $this->x; $j++) {
  39.                 if (isset($ans1[$i][$j]) && isset($ans2[$i][$j]) && $ans1[$i][$j] && $ans2[$i][$j]) {
  40.                     $ans[] = [$i, $j];
  41.                 }
  42.             }
  43.         }
  44.         return $ans;
  45.     }
  47.     function dfs($i, $j, &$ans)
  48.     {
  49.         if (isset($ans[$i][$j]) && $ans[$i][$j]) { //已ok的退出
  50.             return;
  51.         }
  52.         $ans[$i][$j] = 1;
  55.         //往4个方向搜索, 且判断是否能访问
  56.         if ($i - 1 >= 0 && $this->heights[$i - 1][$j] >= $this->heights[$i][$j]) {
  57.             $this->dfs($i - 1, $j, $ans);
  58.         }
  59.         if ($i + 1 < $this->y && $this->heights[$i + 1][$j] >= $this->heights[$i][$j]) {
  60.             $this->dfs($i + 1, $j, $ans);
  61.         }
  62.         if ($j - 1 >= 0 && $this->heights[$i][$j - 1] >= $this->heights[$i][$j]) {
  63.             $this->dfs($i, $j - 1, $ans);
  64.         }
  65.         if ($j + 1 < $this->x && $this->heights[$i][$j + 1] >= $this->heights[$i][$j]) { //这里一开始判断错为y了, 坑了好久
  66.             $this->dfs($i, $j + 1, $ans);
  67.         }
  68.     }
  69. }
  71. echo json_encode((new Solution())->pacificAtlantic([[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]]));
  72. echo PHP_EOL;
  73. echo json_encode((new Solution())->pacificAtlantic([[2, 1], [1, 2]]));
  74. echo PHP_EOL;
  75. echo json_encode((new Solution())->pacificAtlantic([[1, 1], [1, 1], [1, 1]]));
  77. /**
  78.  * 目的是构造出两个答案矩阵 res_1和 res_2，res_k[i][j] = 1 代表格子 (i, j) 能够流向海域，起始从4边开始DFS，所有能够进入队列的格子均能够与海域联通。
  79.  * 最后统计所有满足 res_1[i][j] = res_2[i][j] = 1 的格子即是答案。
  80.  *
  81.  * 执行用时：88 ms, 在所有 PHP 提交中击败了100.00%的用户
  82.  * 内存消耗：21.6 MB, 在所有 PHP 提交中击败了100.00%的用户
  83.  * 通过测试用例：113 / 113
  84.  */