417. 太平洋大西洋水流问题

梦里梦外; 2024-03-31 10:28 30阅读 0赞

### 417. 太平洋大西洋水流问题 ###

有一个 m × n 的矩形岛屿，与 **太平洋** 和 **大西洋** 相邻。 **“太平洋”** 处于大陆的左边界和上边界，而 **“大西洋”** 处于大陆的右边界和下边界。

这个岛被分割成一个由若干方形单元格组成的网格。给定一个 m x n 的整数矩阵 heights ， heights\[r\]\[c\] 表示坐标 (r, c) 上单元格 **高于海平面的高度** 。

岛上雨水较多，如果相邻单元格的高度 **小于或等于** 当前单元格的高度，雨水可以直接向北、南、东、西流向相邻单元格。水可以从海洋附近的任何单元格流入海洋。

返回网格坐标 result 的 **2D 列表** ，其中 result\[i\] = \[ri, ci\] 表示雨水从单元格 (ri, ci) 流动 **既可流向太平洋也可流向大西洋** 。

##### 示例1： #####

![在这里插入图片描述][652d6f5f68c64e79b17a311d5de11990.png]

> 输入: 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\]\]

##### 提示： #####

m = = h e i g h t s . l e n g t h m == heights.length m==heights.length  
 n = = h e i g h t s \[ r \] . l e n g t h n == heights\[r\].length n==heights\[r\].length  
 1 < = m , n < = 200 1 <= m, n <= 200 1<=m,n<=200  
 0 < = h e i g h t s \[ r \] \[ c \] < = 1 0 5 0 <= heights\[r\]\[c\] <= 10^5 0<=heights\[r\]\[c\]<=105

#### 思路：（DFS） ####

*  雨水的流动方向是从高到低，每个单元格上的雨水只能流到高度小于等于当前单元格的相邻单元格。从一个单元格开始，通过搜索的方法模拟雨水的流动，则可以判断雨水是否可以从该单元格流向海洋。
 *  如果直接以每个单元格作为起点模拟雨水的流动，则会重复遍历每个单元格，导致时间复杂度过高。为了降低时间复杂度，可以从矩阵的边界开始反向搜索寻找雨水流向边界的单元格，反向搜索时，每次只能移动到高度相同或更大的单元格。
 *  由于矩阵的左边界和上边界是太平洋，矩阵的右边界和下边界是大西洋，因此从矩阵的左边界和上边界开始反向搜索即可找到雨水流向太平洋的单元格，从矩阵的右边界和下边界开始反向搜索即可找到雨水流向大西洋的单元格。
 *  可以使用深度优先搜索实现 **反向搜索**，搜索过程中需要记录每个单元格是否可以从太平洋反向到达以及是否可以从大西洋反向到达。反向搜索结束之后，遍历每个网格，如果一个网格既可以从太平洋反向到达也可以从大西洋反向到达，则该网格满足太平洋和大西洋都可以到达，将该网格添加到答案中。

#### 代码：（Java） ####

import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.List;
    
    public class dfs_flow_water {
        
    
    	public static void main(String[] args) {
        
    		// TODO 自动生成的方法存根
    		int [][] 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}
    		};
    		List<List<Integer>> ret = pacificAtlantic(heights);
    		System.out.println(ret);
    	}
    	
    	private static int m, n;
    	private static int [][] matrix;
    	private static int [][] direction = {
        {
        0, 1}, {
        0, -1}, {
        1, 0}, {
        -1, 0}};
    	
    	public static List<List<Integer>> pacificAtlantic(int[][] heights) {
        
    		List<List<Integer>> ret = new ArrayList<>();
    		if(heights == null || heights.length == 0) {
        
    			return ret;
    		}
    		m = heights.length;
    		n = heights[0].length;
    		matrix = heights;
    		boolean [][] canReachP = new boolean[m][n];
    		boolean [][] canReachA = new boolean[m][n];
    		
    		for(int i = 0; i < m; i++) {
        
    			dfs(i, 0, canReachP);
    			dfs(i, n-1, canReachA);
    		}
    		for(int i = 0; i < n; i++) {
        
    			dfs(0, i, canReachP);
    			dfs(m-1, i, canReachA);
    		}
    		for(int i = 0; i < m; i++) {
        
    			for(int j = 0; j < n; j++) {
        
    				if(canReachP[i][j] && canReachA[i][j])
    					ret.add(Arrays.asList(i,j));
    			}
    		}
    		
    		return ret;
        }
    
    	private static void dfs(int r, int c, boolean[][] canReach) {
        
    		// TODO 自动生成的方法存根
    		if(canReach[r][c]) {
        
    			return;
    		}
    		canReach[r][c] = true;
    		
    		for(int []d : direction) {
        
    			if(r + d[0] < 0 || r + d[0] >= m || c + d[1] < 0 || c + d[1] >= n || matrix[r+d[0]][c+d[1]] < matrix[r][c])
    				continue;
    			dfs(r+d[0],c+d[1], canReach);
    		}
    	}
    }

##### 输出： #####

![在这里插入图片描述][ce446dc5ad9744f9a6a23d02c95cbf65.png]

##### 复杂度分析： #####

*  时间复杂度：O(mn)，其中 m和 n 分别是矩阵 heights的行数和列数。深度优先搜索最多遍历每个单元格两次，寻找太平洋和大西洋都可以到达的单元格需要遍历整个矩阵，因此时间复杂度是 O(mn)。
 *  空间复杂度：O(mn)，其中 m 和 n分别是矩阵 heights的行数和列数。深度优先搜索的递归调用层数是 O(mn)，记录每个单元格是否可以到达太平洋和大西洋需要 O(mn) 的空间，因此空间复杂度是 O(mn)。

##### 注仅供学习参考！ #####

题目来源：[力扣][Link 1]

[652d6f5f68c64e79b17a311d5de11990.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/20ea453d93f24f92b5b6b5f357699da7.png
[ce446dc5ad9744f9a6a23d02c95cbf65.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/18bec007d44a4af9b055f61e3dc58b8f.png
[Link 1]: https://leetcode.cn/problems/pacific-atlantic-water-flow/description/