-
Notifications
You must be signed in to change notification settings - Fork 713
/
main2.cpp
165 lines (128 loc) · 4.7 KB
/
main2.cpp
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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
/// Source : https://leetcode.com/problems/pacific-atlantic-water-flow/
/// Author : liuyubobobo
/// Time : 2022-08-19
#include <iostream>
#include <vector>
#include <set>
using namespace std;
/// DFS from inside to outside
/// Shrink vertex to remove all the cycles from the underlying search graph
/// Time Complexity: O(R * C)
/// Space Complexity: O(R * C)
class UF{
private:
vector<int> parent;
public:
UF(int n) : parent(n){
for(int i = 0 ; i < n ; i ++)
parent[i] = i;
}
int find(int p){
if(p != parent[p])
parent[p] = find(parent[p]);
return parent[p];
}
bool is_connected(int p, int q){
return find(p) == find(q);
}
void union_elements(int p, int q){
int p_root = find(p), q_root = find(q);
if(p_root == q_root) return;
parent[p_root] = q_root;
}
};
class Solution {
private:
const int dirs[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
int R, C;
public:
vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
R = heights.size(), C = heights[0].size();
// uf 有 R * C 个节点。
UF uf(R * C);
vector<vector<bool>> visited(R, vector<bool>(C, false));
for(int i = 0; i < R; i ++)
for(int j = 0; j < C; j ++){
// 缩点
if(!visited[i][j]){
vector<int> cc;
dfs_cc(heights, i, j, visited, cc);
for(int i = 1; i < cc.size(); i ++)
uf.union_elements(cc[0], cc[i]);
}
}
// 根据缩好的点,创建新图,这张图是 DAG
// 注意,这张图有 R * C + 2 个节点,索引 R * C 对应 pacific,索引 R * C + 1 对应 atlantic
vector<set<int>> g(R * C + 2);
for(int x = 0; x < R; x ++)
for(int y = 0; y < C; y ++){
// u 是 [x, y] 缩点后对应的点编号
int u = uf.find(x * C + y);
for(int d = 0; d < 4; d ++){
int nx = x + dirs[d][0], ny = y + dirs[d][1];
if(!in_area(nx, ny)) continue;
// v 是 [nx, ny] 缩点后对应的点编号
int v = uf.find(nx * C + ny);
if(u == v) continue;
// 注意,此时 height 的比较,可以扔掉 = 了,
// 因为 u 和 v 不是缩点后的一个节点,所以高度肯定不等
if(heights[x][y] > heights[nx][ny]) g[u].insert(v);
}
if(x == 0 || y == 0) g[u].insert(R * C);
if(x == R - 1 || y == C - 1) g[u].insert(R * C + 1);
}
// 现在,可以在 g 这张新图上,做记忆化搜索了。
// 因为这张图上边的方向已经代表了从高的地方走向低的地方,所以不需要再使用 height 数组了。
// 但是,因为建图的方式,我们的搜索是从高向地进行的。
vector<int> pacific(R * C + 2, -1), atlantic(R * C + 2, -1);
for(int u = 0; u < R * C; u ++){
if(pacific[u] == -1) dfs(g, u, pacific, atlantic);
}
vector<vector<int>> res;
for(int i = 0; i < R; i ++)
for(int j = 0; j < C; j ++){
int u = uf.find(i * C + j);
if(pacific[u] == 1 && atlantic[u] == 1)
res.push_back({i, j});
}
return res;
}
private:
void dfs_cc(const vector<vector<int>>& H, int x, int y,
vector<vector<bool>>& visited, vector<int>& cc){
visited[x][y] = true;
cc.push_back(x * C + y);
for(int d = 0; d < 4; d ++){
int nx = x + dirs[d][0], ny = y + dirs[d][1];
if(in_area(nx, ny) && !visited[nx][ny] && H[x][y] == H[nx][ny])
dfs_cc(H, nx, ny, visited, cc);
}
}
void dfs(const vector<set<int>>& g, int u,
vector<int>& pacific, vector<int>& atlantic){
if(u == R * C) pacific[u] = 1;
if(u == R * C + 1) atlantic[u] = 1;
if(pacific[u] != -1) return;
for(int v: g[u]){
dfs(g, v, pacific, atlantic);
if(pacific[v] == 1) pacific[u] = 1;
if(atlantic[v] == 1) atlantic[u] = 1;
}
if(pacific[u] != 1) pacific[u] = 0;
if(atlantic[u] != 1) atlantic[u] = 0;
}
bool in_area(int x, int y){
return 0 <= x && x < R && 0 <= y && y < C;
}
};
int main() {
vector<vector<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}
};
Solution().pacificAtlantic(heights);
return 0;
}