959. Regions Cut By Slashes
## 思路
對點做UnionFind
如果兩點的root一樣 表示他再切割出了一個area
## Code
```python
class UnionFind:
def __init__(self, n):
self.n = n
self.root = list(range(n * n))
self.rank = [1] * (n * n)
def get_id(self, r, c):
return r * self.n + c
def find(self, x):
if x != self.root[x]:
self.root[x] = self.find(self.root[x])
return self.root[x]
def union(self, r1, c1, r2, c2):
x = self.get_id(r1, c1)
y = self.get_id(r2, c2)
rx, ry = self.find(x), self.find(y)
if rx == ry:
return 1
if self.rank[rx] >= self.rank[ry]:
self.rank[rx] += self.rank[ry]
self.root[ry] = rx
else:
self.rank[ry] += self.rank[rx]
self.root[rx] = ry
return 0
class Solution:
def regionsBySlashes(self, grid: List[str]) -> int:
n = len(grid)+1
uf = UnionFind(n)
res = 1
# border
for r in range(n):
uf.union(r-1, 0, r, 0)
uf.union(r-1, n-1, r, n-1)
for c in range(n):
uf.union(0, c-1, 0, c)
uf.union(n-1, c-1, n-1, c)
for r in range(n-1):
for c in range(n-1):
if grid[r][c] == '/':
res += uf.union(r, c+1, r+1, c)
elif grid[r][c] == '\\':
res += uf.union(r, c, r+1, c+1)
return res
```