本文最后更新于：2021年1月28日 晚上
给定一个 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]] (上图中带括号的单元).
|
Solution
参考 @da-li-wang
- 广度优先搜索
- 构建一个状态矩阵：用第一个bit存储太平洋是否能达到此点；用第二个bit存储大西洋是否能达到此点。
- 最终查询点状态为3（二进制为11）的点即可。
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
57
58
59
60
61
62
|
class Solution {
private:
int d[4][2] = {{-1,0}, {1,0}, {0,-1}, {0,1}};
int m, n;
bool inArea(int x, int y){
return x>=0 && x<m && y>=0 && y<n;
}
public:
vector<vector<int>> pacificAtlantic(vector<vector<int>>& matrix) {
vector<vector<int>> res;
m = matrix.size();
if(m==0) return res;
n = matrix[0].size();
if(n==0) return res;
vector<vector<int>> status(m, vector<int>(n, 0));
queue<pair<int,int>> q;
for(int i=0; i<m; ++i){
q.push({i,0});
status[i][0] |= 1;
q.push({i,n-1});
status[i][n-1] |= 2;
}
for(int j=0; j<n; ++j){
q.push({0,j});
status[0][j] |= 1;
q.push({m-1,j});
status[m-1][j] |= 2;
}
while(!q.empty()){
auto pos = q.front();
q.pop();
int x = pos.first;
int y = pos.second;
for(int i=0; i<4; ++i){
int newx = x+d[i][0];
int newy = y+d[i][1];
if(inArea(newx, newy) && matrix[newx][newy] >= matrix[x][y]){
if(status[newx][newy] != status[x][y]){
status[newx][newy] |= status[x][y];
q.push({newx,newy});
}
}
}
}
for(int i=0; i<m; ++i){
for(int j=0; j<n; ++j){
if(status[i][j]==3)
res.push_back({i,j});
}
}
return res;
}
};
|