本文最后编辑于 前，其中的内容可能需要更新。
力扣417.太平洋大西洋水流问题题解
给定一个 m x n 的非负整数矩阵来表示一片大陆上各个单元格的高度。“太平洋”处于大陆的左边界和上边界，而“大西洋”处于大陆的右边界和下边界。
规定水流只能按照上、下、左、右四个方向流动，且只能从高到低或者在同等高度上流动。
请找出那些水流既可以流动到“太平洋”，又能流动到“大西洋”的陆地单元的坐标。
提示：
输出坐标的顺序不重要
m 和 n 都小于150
示例：
1
2
3
4
5
6
7
8
9
10
11
12
13
| 给定下面的 5x5 矩阵:
太平洋 ~ ~ ~ ~ ~
~ 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]] (上图中带括号的单元).
|
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/pacific-atlantic-water-flow
看到上面的文本解释的时候直接一脸懵逼， 我们直接来看力扣给的示例
首先来看一下这个二维数组(代码有提现)的左下角，数字5
首先这个数字被打了括号，那么这个数字的位置就是题目中的“水流既可以流动到“太平洋”，又能流动到“大西洋”的陆地单元的坐标”，看一下图中的箭头，左边是太平洋，下边是大西洋，这个5的位置和两大洋接壤，即可以流到两洋。
第一个区块解释完毕就可以大致看出来题目要求了，在看一下这个5旁边的1
可以理解为单元格想要满足同时流向两大洋的条件就是(不管具体路径)下一个格子必须比上一个格子的点数要小或者等于，才能判断为水流能流向，比如这个
这个位置的水流可以流到这几个位置上，所以这个位置是满足题目要求的
返回要求：
一看就是返回的数组位置咯
解题思路
我们可以把这个返回结果看成是把可以到达太平洋和可以到达大西洋的大陆板块取了交集，那么我们首先需要求出分别到达大西洋和太平洋的大陆板块，这两个过程又是一模一样，那么我们首先来求解到达大西洋的大陆板块。
我是用的是dfs算法，因为很明显用dfs可以轻易地逆推出结果，把结果打上标记
最后再来个数组遍历，就可以找到最后的结果了
那么直接来看代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
| class Solution {
int row,col;
private int [][] directions = {{-1,0},{0,1},{1,0},{0,-1}};
private int[][] heights;
public List<List<Integer>> pacificAtlantic(int[][] heights) {
List<List<Integer>> result = new ArrayList<>();
if(heights == null || heights.length == 0){
return result;
}
row = heights.length;
col = heights[0].length;
boolean[][] canReachPacific = new boolean[row][col];
boolean[][] canReachAtlantic = new boolean[row][col];
this.heights = heights;
for(int i = 0; i < row; ++i){
dfs(i, 0, canReachPacific);
dfs(i, col - 1 ,canReachAtlantic);
}
for(int j = 0; j < col; ++j){
dfs(0, j, canReachPacific);
dfs(row - 1, j, canReachAtlantic);
}
for(int i = 0; i < row; ++i){
for(int j = 0; j < col; ++j){
if(canReachPacific[i][j] && canReachAtlantic[i][j])
{
result.add(Arrays.asList(i,j));
}
}
}
return result;
}
private void dfs(int r, int c,boolean[][] canReach){
if(canReach[r][c]){
return;
}
canReach[r][c] = true;
for(int[] d : directions){
int nextR = r + d[0];
int nextC = c + d[1];
if(nextR < 0 || nextR >= row || nextC < 0 || nextC >= col || heights[r][c] > heights[nextR][nextC]){
continue;
}
dfs(nextR, nextC, canReach);
}
}
}
|
结果
