代码随想录 417.太平洋大西洋水流问题

思路：本题的起点（所求答案）不明确，但是终点（上下左右四个边界）明确。所以从边界出发可以更方便地找到答案。

1.边界：heights中的i = 0或者i = m - 1;或者j = 0或者j = n - 1的格子。

2.答案：既可流向太平洋也可流向大西洋的格子。

（1）对于可流向太平洋的格子，从上边界（i = 0）和左边界（j = 0）倒着往高处走，所有能访问到的格子都是可以流向太平洋的格子。

（2）对于可流向大西洋的格子，从下边界（i = m - 1）和右边界（j = n - 1）倒着往高处走，所有能访问到的格子都是可以流向大西洋的格子。

3.计算这两类格子的交集，就是既可流向太平洋也可流向大西洋的格子。

附代码：

class Solution { //左右上下 private static final int[][] DIRS = {{0,-1},{0,1},{-1,0},{1,0}}; public List<List<Integer>> pacificAtlantic(int[][] heights) { int m = heights.length,n = heights[0].length; //从太平洋边界出发 boolean[][] pacificVis = new boolean[m][n]; for(int j = 0;j < n;j++){ dfs(0,j,pacificVis,heights); //上边界 } for(int i = 1;i < m;i++){ dfs(i,0,pacificVis,heights); //左边界，i从1开始是因为（0，0）已经包含在上边界中 } //从大西洋边界出发 boolean[][] atlanticVis = new boolean[m][n]; for(int j = 0;j < n;j++){ dfs(m - 1,j,atlanticVis,heights); //下边界 } for(int i = 0;i < m - 1;i++){ dfs(i,n - 1,atlanticVis,heights); //右边界 最后一列是m - 2是因为（m - 1,n - 1）已经包含在下边界中 } //交集即为答案 List<List<Integer>> res = new ArrayList<>(); for(int i = 0;i < m;i++){ for(int j = 0;j < n;j++){ if(pacificVis[i][j] && atlanticVis[i][j]){ res.add(List.of(i,j)); } } } return res; } private void dfs(int i,int j,boolean[][] vis,int[][] heights){ if(vis[i][j]){ //避免重复访问，避免反复横跳无限递归 return; } vis[i][j] = true; //标记(i,j)已访问 for(int[] d : DIRS){//枚举相邻格子 int x = i + d[0],y = j + d[1]; if(x >= 0 && x < heights.length && y >= 0 && y < heights[x].length && heights[x][y] >= heights[i][j]){ //往高处走 dfs(x,y,vis,heights); } } } }