题目

类型：DFS
image.png

解题思路

雨水的流动方向是从高到低，每个单元格上的雨水只能流到高度小于等于当前单元格的相邻单元格。从一个单元格开始，通过搜索的方法模拟雨水的流动，则可以判断雨水是否可以从该单元格流向海洋。

如果直接以每个单元格作为起点模拟雨水的流动，则会重复遍历每个单元格，导致时间复杂度过高。为了降低时间复杂度，可以从矩阵的边界开始反向搜索寻找雨水流向边界的单元格，反向搜索时，每次只能移动到高度相同或更大的单元格。

由于矩阵的左边界和上边界是太平洋，矩阵的右边界和下边界是大西洋，因此从矩阵的左边界和上边界开始反向搜索即可找到雨水流向太平洋的单元格，从矩阵的右边界和下边界开始反向搜索即可找到雨水流向大西洋的单元格。

可以使用深度优先搜索实现反向搜索，搜索过程中需要记录每个单元格是否可以从太平洋反向到达以及是否可以从大西洋反向到达。反向搜索结束之后，遍历每个网格，如果一个网格既可以从太平洋反向到达也可以从大西洋反向到达，则该网格满足太平洋和大西洋都可以到达，将该网格添加到答案中。

代码

  1. class Solution {
  2.     static int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
  3.     int[][] heights;
  4.     int m, n;
  6.     public List<List<Integer>> pacificAtlantic(int[][] heights) {
  7.         this.heights = heights;
  8.         this.m = heights.length;
  9.         this.n = heights[0].length;
  10.         boolean[][] pacific = new boolean[m][n];
  11.         boolean[][] atlantic = new boolean[m][n];
  12.         for (int i = 0; i < m; i++) {
  13.             dfs(i, 0, pacific);
  14.         }
  15.         for (int j = 1; j < n; j++) {
  16.             dfs(0, j, pacific);
  17.         }
  18.         for (int i = 0; i < m; i++) {
  19.             dfs(i, n - 1, atlantic);
  20.         }
  21.         for (int j = 0; j < n - 1; j++) {
  22.             dfs(m - 1, j, atlantic);
  23.         }
  24.         List<List<Integer>> result = new ArrayList<List<Integer>>();
  25.         for (int i = 0; i < m; i++) {
  26.             for (int j = 0; j < n; j++) {
  27.                 if (pacific[i][j] && atlantic[i][j]) {
  28.                     List<Integer> cell = new ArrayList<Integer>();
  29.                     cell.add(i);
  30.                     cell.add(j);
  31.                     result.add(cell);
  32.                 }
  33.             }
  34.         }
  35.         return result;
  36.     }
  38.     public void dfs(int row, int col, boolean[][] ocean) {
  39.         if (ocean[row][col]) {
  40.             return;
  41.         }
  42.         ocean[row][col] = true;
  43.         for (int[] dir : dirs) {
  44.             int newRow = row + dir[0], newCol = col + dir[1];
  45.             if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && heights[newRow][newCol] >= heights[row][col]) {
  46.                 dfs(newRow, newCol, ocean);
  47.             }
  48.         }
  49.     }
  50. }