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 ``` -- http://i.imgur.com/OLvBn3b.jpg -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 185.213.82.145 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1723261113.A.4C2.html