原文链接: https://leetcode-cn.com/problems/pacific-atlantic-water-flow
英文原文
There is an m x n rectangular island that borders both the Pacific Ocean and Atlantic Ocean. The Pacific Ocean touches the island's left and top edges, and the Atlantic Ocean touches the island's right and bottom edges.
The island is partitioned into a grid of square cells. You are given an m x n integer matrix heights where heights[r][c] represents the height above sea level of the cell at coordinate (r, c).
The island receives a lot of rain, and the rain water can flow to neighboring cells directly north, south, east, and west if the neighboring cell's height is less than or equal to the current cell's height. Water can flow from any cell adjacent to an ocean into the ocean.
Return a 2D list of grid coordinates result where result[i] = [ri, ci] denotes that rain water can flow from cell (ri, ci) to both the Pacific and Atlantic oceans.
Example 1:
Input: 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]] Output: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]
Example 2:
Input: heights = [[2,1],[1,2]] Output: [[0,0],[0,1],[1,0],[1,1]]
Constraints:
m == heights.lengthn == heights[r].length1 <= m, n <= 2000 <= heights[r][c] <= 105
中文题目
给定一个 m x n 的非负整数矩阵来表示一片大陆上各个单元格的高度。“太平洋”处于大陆的左边界和上边界，而“大西洋”处于大陆的右边界和下边界。
规定水流只能按照上、下、左、右四个方向流动，且只能从高到低或者在同等高度上流动。
请找出那些水流既可以流动到“太平洋”，又能流动到“大西洋”的陆地单元的坐标。
提示：
- 输出坐标的顺序不重要
- m 和 n 都小于150
示例：
给定下面的 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]] (上图中带括号的单元).
通过代码
高赞题解
解题思路
对于此题我们可以直观的取暴力搜索每一个点是否可以达到两边的大洋，当然这样子要处理的东西会很多，并且思路不够明显。有小伙伴会说，水怎么能往高处流动，现实生活中水当然是往低处流的。但是现在键盘在你手上，你让他往东流他能往西流？
咱这是能上天的黄河之水！
对于一个点它能流动两边的大洋，那么反过来，两边大洋的水反着流就能达到这个点。
尽然水开始倒流了，那么逻辑也需要反过来，因此只有将下一个点比当前的点大时或者等于当前点的高度时，水才能流过去。
找出所有这样的点我们需要怎么做？
- 找出所有从太平洋出发的水所能达到的点
- 找出所有从大西洋出发的水所能达到的点
- 这些重合的点便是我们要找的点
写良心的题解真的不易，点个关注点个👍吧各位！
代码
class Solution {
public:
vector<vector<int>> P, A, ans;
int n, m;
vector<vector<int>> pacificAtlantic(vector<vector<int>>& M) {
n = M.size(), m = M[0].size();
P = A = vector<vector<int>>(n, vector<int>(m, 0));
//左右两边加上下两边出发深搜
for(int i = 0; i < n; ++i) dfs(M, P, i, 0), dfs(M, A, i, m - 1);
for(int j = 0; j < m; ++j) dfs(M, P, 0, j), dfs(M, A, n - 1, j);
return ans;
}
void dfs(vector<vector<int>>& M, vector<vector<int>>& visited, int i, int j){
if(visited[i][j]) return;
visited[i][j] = 1;
if(P[i][j] && A[i][j]) ans.push_back({i,j});
//上下左右深搜
if(i-1 >= 0 && M[i-1][j] >= M[i][j]) dfs(M, visited, i-1, j);
if(i+1 < n && M[i+1][j] >= M[i][j]) dfs(M, visited, i+1, j);
if(j-1 >= 0 && M[i][j-1] >= M[i][j]) dfs(M, visited, i, j-1);
if(j+1 < m && M[i][j+1] >= M[i][j]) dfs(M, visited, i, j+1);
}
};统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 30002 | 61849 | 48.5% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
