-
-
Notifications
You must be signed in to change notification settings - Fork 31
Expand file tree
/
Copy pathSurrounded Regions.java
More file actions
executable file
·191 lines (166 loc) · 5.58 KB
/
Copy pathSurrounded Regions.java
File metadata and controls
executable file
·191 lines (166 loc) · 5.58 KB
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
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
M
1520479490
tags: DFS, BFS, Union Find, Matrix DFS
给一个2D board, 里面是 'X' 和 'O'. 把所有被X包围的area都涂成'X'.
从四个边的edge出发, 像感染僵尸病毒一样扩散, 把靠边的node全部mark, 然后将还是'O'的改成X, 最后回复marks -> 'O'
#### Union Find
- UnionFind里面这次用到了一个rank的概念, 需要review. rank[] 也就是在tracking每一个node所在union的size.
- 目的是: always并到大的union里面
- note: 将2D coordinate (x,y) 转换成1D: index = x * n + y
#### DFS: mark all invalid 'O'
- Reversed thinking: find surrounded nodes, how about filter out border nodes && their connections?
- Need to traverse all the border nodes, consider dfs, visit all.
- loop over border: find any 'O', and dfs to find all connected nodes, mark them as 'M'
- time: O(mn) loop over all nodes to replace remaining 'O' with 'X'
#### DFS: mark all valid 'O'
- More like a graph problem: traverse all 'O' spots, and mark as visited int[][] with area count [1 -> some number]
- Run dfs as top->bottom: mark area count and dsf into next level
- End condition: if any 'O' reaches border, mark the global map<count, false>
- keep dfs untill all connected nodes are visited.
- At the end, O(mn) loop over the matrix and mark 'X' for all the true area from map.
- Practice: write code to verify
### BFS
- TODO
```
/*
Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'.
A region is captured by flipping all 'O's into 'X's in that surrounded region.
For example,
X X X X
X O O X
X X O X
X O X X
After running your function, the board should be:
X X X X
X X X X
X X X X
X O X X
Hide Tags Breadth-first Search
*/
// DFS
public class Solution {
private int[] dx = {1, -1, 0, 0};
private int[] dy = {0, 0, 1, -1};
public void solve(char[][] board) {
if (board == null || board.length == 0) {
return;
}
int row = board.length;
int col = board[0].length;
//Check the board
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (i == 0 || i == row - 1 || j == 0 || j == col - 1) {
fill(board, i , j);
}
}
}
char mark = 'M', candidate = 'O', goal = 'X';
//Replacement
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (board[i][j] == candidate) {
board[i][j] = goal;
}
if (board[i][j] == mark) {
board[i][j] = candidate;
}
}
}
}
//DFS to traverse all border nodes and their connected nodes
public void fill(char[][] board, int x, int y) {
int row = board.length, col = board[0].length;
if (x < 0 || x >= row || y < 0 || y >= col || board[x][y] != 'O') {
return;
}
board[x][y] = 'M';
for (int i = 0; i < dx.length; i++) {
fill(board, x + dx[i], y + dy[i]);
}
}
}
/*
Thoughts:
The only where it can't be surrounded is when the O is on edge; also, same to any connecting O with it.
1. Find all edging O and union all the neighbors, mark them differently
2. Assign all other positiions to X if not alreay is.
3. Flip marked positions back to O
Use union the 4 directions of O to mark them
*/
class Solution {
public void solve(char[][] board) {
if (board == null || board.length == 0 || board[0] == null || board[0].length == 0) {
return;
}
int m = board.length;
int n = board[0].length;
UnionFind unionFind = new UnionFind(m * n + 1);
int root = m * n;
int[] dx = {0, 0, 1, -1};
int[] dy = {1, -1, 0, 0};
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == 'X') {
continue;
}
int curr = i * n + j;
// Merging the edge with the virtual root position
if (i == 0 || j == 0 || i == m - 1 || j == n - 1) {
unionFind.union(curr, root);
continue;
}
// If edge is 'O', union them.
for (int k = 0; k < dx.length; k++) {
int x = i + dx[k];
int y = j + dy[k];
if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O') {
unionFind.union(curr, x * n + y);
}
}
}
}
// Assign 'X'
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == 'O' && unionFind.find(i * n + j) != root) {
board[i][j] = 'X';
}
}
}
}
}
class UnionFind {
int[] father;
int[] rank;
public UnionFind(int x) {
father = new int[x];
rank = new int[x];
for (int i = 0; i < x; i++) {
father[i] = i;
}
rank[x - 1] = x;
}
public void union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX == rootY) {
return;
}
if (rank[rootX] < rank[rootY]) {
father[rootX] = rootY;
} else {
if (rank[rootX] == rank[rootY]) {
rank[rootX]++;
}
father[rootY] = rootX;
}
}
public int find(int x) {
if (father[x] == x) {
return x;
}
return father[x] = find(father[x]);
}
}
```