959 Regions Cut By Slashes
1. Question
In a N x N grid
composed of 1 x 1 squares, each 1 x 1 square consists of a/
,\
, or blank space. These characters divide the square into contiguous regions.
(Note that backslash characters are escaped, so a\
is represented as"\\"
.)
Return the number of regions.
Example 1:
Input:
[
" /",
"/ "
]
Output: 2
Example 2:
Input:
[
" /",
" "
]
Output: 1
Note:
1 <= grid.length == grid[0].length <= 30
grid[i][j]
is either'/'
,'\'
, or' '
.
2. Implementation
(1) Union Find
思路: 将一个square分成4个部分,将top标记为0, right标记为1, bottom标记2, left标记3. union包含两部分:
inner connection: 一开始squaure里的四个部分是分离的,如果当前square的字符是'/', 将0,3合并,1,2合并。如果是'\', 将0, 1合并,2, 3合并。如果是“ ”, 将0,1,2,3合并
inter connection: 将两两square合并,由于我们从左到右,上到下的顺序遍历grid,所以我们将当前square的top(0)和上面的square的bottom(2)合并,将当前square的left(3)和左边的square的right(1)合并
union结束后,计算component的数量即可
class Solution {
public int regionsBySlashes(String[] grid) {
int n = grid.length;
int size = n * n * 4;
UnionFind uf = new UnionFind(size);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i > 0) uf.union(id(i - 1, j, 2, n), id(i, j, 0, n));
if (j > 0) uf.union(id(i, j - 1, 1, n),id(i, j, 3, n));
if (grid[i].charAt(j) == '/') {
uf.union(id(i, j, 0, n), id(i, j, 3, n));
uf.union(id(i, j, 1, n), id(i, j, 2, n));
}
else if (grid[i].charAt(j) == '\\') {
uf.union(id(i, j, 0, n), id(i, j, 1, n));
uf.union(id(i, j, 2, n), id(i, j, 3, n));
}
else {
uf.union(id(i, j, 0, n), id(i, j, 1, n));
uf.union(id(i, j, 2, n), id(i, j, 3, n));
uf.union(id(i, j, 0, n), id(i, j, 3, n));
}
}
}
return uf.count;
}
public int id(int row, int col, int offset, int n) {
return (row * n + col) * 4 + offset;
}
class UnionFind {
int[] root;
int[] size;
int count;
public UnionFind(int n) {
root = new int[n];
size = new int[n];
count = n;
for (int i = 0; i < n; i++) {
root[i] = i;
size[i] = 1;
}
}
public int find(int node) {
while (node != root[node]) {
node = root[node];
}
return node;
}
public void union(int i , int j) {
int p = find(i);
int q = find(j);
if (p == q) return;
if (size[p] < size[q]) {
root[p] = q;
size[q] += size[p];
}
else {
root[q] = p;
size[p] += size[q];
}
--count;
}
}
}
3. Time & Space Complexity
时间复杂度O(n^2), 空间复杂度O(n^2)
Last updated
Was this helpful?