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
Explanation: The 2x2 grid is as follows:



Example 2:
Input:
[
  " /",
  "  "
]
Output: 1
Explanation: The 2x2 grid is as follows:



Example 3:
Input:
[
  "\\/",
  "/\\"
]
Output: 4
Explanation: (Recall that because \ characters are escaped, "\\/" refers to \/, and "/\\" refers to /\.)
The 2x2 grid is as follows:



Example 4:
Input:
[
  "/\\",
  "\\/"
]
Output: 5
Explanation: (Recall that because \ characters are escaped, "/\\" refers to /\, and "\\/" refers to \/.)
The 2x2 grid is as follows:



Example 5:
Input:
[
  "//",
  "/ "
]
Output: 3
Explanation: The 2x2 grid is as follows:


 
Note:

1 <= grid.length == grid[0].length <= 30
grid[i][j] is either '/', '\', or ' '.

Source: leetcode | Difficulty: MEDIUM
Tags: Spanning trees

Graph algorithms

Graph traversal

Starter code: class Solution:
    def regionsBySlashes(self, grid: List[str]) -> int:
        

Solutions:
from itertools import chain

class Solution:

	def regionsBySlashes(self, grid):
		grid = self.convert_grid(grid)
		print(*(list(map(str, x)) for x in grid), sep='')
		return len([self.destroy_island(x, y, grid) for y in range(len(grid)) for (x, v) in enumerate(grid[y]) if v == 0])

	@staticmethod
	def convert_grid(grid):
		new_grid = [[0] * len(grid[0]) * 2 for _ in range(len(grid) * 2)]
		for (x, y, v) in ((x, y, v) for y in range(len(grid)) for (x, v) in enumerate(grid[y]) if v in '\\\\/'):
			new_grid[y * 2 + 0][x * 2 + (1 if v == '/' else 0)] = v
			new_grid[y * 2 + 1][x * 2 + (0 if v == '/' else 1)] = v
		return new_grid

	def destroy_island(self, x, y, grid):
		grid[y][x] = 1
		for c in Solution.search(x, y, grid):
			self.destroy_island(c[0], c[1], grid)

	@staticmethod
	def search(x, y, grid):
		in_bounds = lambda c: 0 <= c[1] < len(grid) and 0 <= c[0] < len(grid[c[1]])
		check_orthog = lambda c: in_bounds(c) and grid[c[1]][c[0]] == 0

		def check_diag(c):
			if not in_bounds(c) or grid[c[1]][c[0]] != 0:
				return False
			(d_x, d_y) = (c[0] - x, c[1] - y)
			sep = '\\\\' if d_x > 0 > d_y or d_x < 0 < d_y else '/'
			return not (grid[y + d_y][x] == sep and grid[y][x + d_x] == sep)
		yield from chain(filter(check_orthog, ((x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1))), filter(check_diag, ((x + 1, y + 1), (x + 1, y - 1), (x - 1, y + 1), (x - 1, y - 1))))


class DSU:

	def __init__(self):
		self.parent = {}

	def find(self, x):
		if x not in self.parent:
			self.parent[x] = x
		if self.parent[x] != x:
			self.parent[x] = self.find(self.parent[x])
		return self.parent[x]

	def union(self, x, y):
		(xroot, yroot) = (self.find(x), self.find(y))
		if xroot != yroot:
			self.parent[yroot] = xroot

class Solution:

	def regionsBySlashes(self, grid: List[str]) -> int:
		n = len(grid)
		dsu = DSU()
		for i in range(n):
			for j in range(n):
				if i > 0:
					dsu.union((i - 1, j, 2), (i, j, 0))
				if j > 0:
					dsu.union((i, j - 1, 1), (i, j, 3))
				if grid[i][j] != '/':
					dsu.union((i, j, 0), (i, j, 1))
					dsu.union((i, j, 2), (i, j, 3))
				if grid[i][j] != '\\\\':
					dsu.union((i, j, 3), (i, j, 0))
					dsu.union((i, j, 1), (i, j, 2))
		seen = set()
		for key in dsu.parent.keys():
			temp = dsu.find(key)
			seen.add(temp)
		return len(seen)


from typing import List

class DS:

	def __init__(self, n):
		self.sizes = [1] * n
		self.roots = [i for i in range(n)]

	def query(self, x):
		root = x
		while root != self.roots[root]:
			self.roots[root] = self.roots[self.roots[root]]
			root = self.roots[root]
		return root

	def union(self, x, y):
		(xRoot, yRoot) = (self.query(x), self.query(y))
		(s, l) = (xRoot, yRoot) if self.sizes[xRoot] < self.sizes[yRoot] else (yRoot, xRoot)
		self.roots[s] = l
		self.sizes[l] += self.sizes[s]

class Solution:

	def regionsBySlashes(self, grid: List[str]) -> int:
		n = len(grid)
		nodes = DS(4 * n * n)
		getIndex = lambda r, c, k: 4 * (n * r + c) + k
		for i in range(n):
			for j in range(n):
				if i > 0:
					nodes.union(getIndex(i, j, 0), getIndex(i - 1, j, 2))
				if i < n - 1:
					nodes.union(getIndex(i, j, 2), getIndex(i + 1, j, 0))
				if j > 0:
					nodes.union(getIndex(i, j, 3), getIndex(i, j - 1, 1))
				if j < n - 1:
					nodes.union(getIndex(i, j, 1), getIndex(i, j + 1, 3))
				if grid[i][j] != '/':
					nodes.union(getIndex(i, j, 0), getIndex(i, j, 1))
					nodes.union(getIndex(i, j, 3), getIndex(i, j, 2))
				if grid[i][j] != '\\\\':
					nodes.union(getIndex(i, j, 0), getIndex(i, j, 3))
					nodes.union(getIndex(i, j, 1), getIndex(i, j, 2))
		return sum((i == nodes.query(i) for i in range(4 * n * n)))


class Solution:
	f = {}

	def find(self, x):
		self.f.setdefault(x, x)
		if self.f[x] != x:
			self.f[x] = self.find(self.f[x])
		return self.f[x]

	def union(self, x, y):
		self.f[self.find(x)] = self.find(y)

	def regionsBySlashes(self, grid: List[str]) -> int:
		self.f = {}
		for row in range(len(grid)):
			for col in range(len(grid)):
				if row:
					self.union((row - 1, col, 2), (row, col, 0))
				if col:
					self.union((row, col - 1, 3), (row, col, 1))
				if grid[row][col] != '/':
					self.union((row, col, 0), (row, col, 3))
					self.union((row, col, 1), (row, col, 2))
				if grid[row][col] != '\\\\':
					self.union((row, col, 0), (row, col, 1))
					self.union((row, col, 2), (row, col, 3))
		return len(set(map(self.find, self.f)))


class Solution:

	def regionsBySlashes(self, grid: List[str]) -> int:
		for i in range(len(grid)):
			grid[i] = grid[i].replace('\\\\', '*')
		N = len(grid)
		record = [[[0, 0, 0, 0] for j in range(N)] for i in range(N)]
		count = 0

		def dfs(i, j, k):
			if 0 <= i < N and 0 <= j < N and (record[i][j][k] == 0):
				if grid[i][j] == '*':
					if k <= 1:
						record[i][j][0] = record[i][j][1] = count
						dfs(i - 1, j, 2)
						dfs(i, j + 1, 3)
					else:
						record[i][j][2] = record[i][j][3] = count
						dfs(i + 1, j, 0)
						dfs(i, j - 1, 1)
				elif grid[i][j] == '/':
					if 1 <= k <= 2:
						record[i][j][1] = record[i][j][2] = count
						dfs(i + 1, j, 0)
						dfs(i, j + 1, 3)
					else:
						record[i][j][0] = record[i][j][3] = count
						dfs(i - 1, j, 2)
						dfs(i, j - 1, 1)
				else:
					record[i][j][0] = record[i][j][1] = record[i][j][2] = record[i][j][3] = count
					dfs(i - 1, j, 2)
					dfs(i, j + 1, 3)
					dfs(i + 1, j, 0)
					dfs(i, j - 1, 1)
		for i in range(N):
			for j in range(N):
				for k in range(4):
					if record[i][j][k] == 0:
						count += 1
						dfs(i, j, k)
		return count


class Solution:

	def regionsBySlashes(self, grid: List[str]) -> int:
		N = len(grid)
		matrix = [list(s) for s in grid]
		parent = list(range(N * N * 4))
		print(parent)

		def find(x):
			depth = 0
			while parent[x] != x:
				x = parent[x]
				depth += 1
			return (x, depth)

		def union(x, y):
			print((x, y))
			((rx, dx), (ry, dy)) = (find(x), find(y))
			if dx < dy:
				parent[rx] = ry
			else:
				parent[ry] = rx

		def isValid(i, j):
			if i >= N or i < 0 or j >= N or (j < 0):
				return False
			return True
		for i in range(N):
			for j in range(N):
				idtop = (i * N + j) * 4
				if matrix[i][j] == '/':
					union(idtop + 1, idtop + 2)
					union(idtop, idtop + 3)
				elif matrix[i][j] == '\\\\':
					union(idtop, idtop + 1)
					union(idtop + 2, idtop + 3)
				else:
					union(idtop, idtop + 1)
					union(idtop, idtop + 2)
					union(idtop, idtop + 3)
				if isValid(i - 1, j):
					union(idtop, 4 * ((i - 1) * N + j) + 2)
				if isValid(i, j - 1):
					union(idtop + 3, 4 * (i * N + j - 1) + 1)
		return len(set((find(x)[0] for x in range(4 * N * N))))


class Solution:

	def regionsBySlashes(self, grid: List[str]) -> int:
		(m, n) = (len(grid), len(grid[0]))
		print(m, n)
		mat = [[0] * (4 * n) for _ in range(4 * m)]
		for i in range(m):
			for j in range(n):
				if grid[i][j] == '/':
					mat[4 * i][4 * j + 3] = 1
					mat[4 * i + 1][4 * j + 2] = 1
					mat[4 * i + 2][4 * j + 1] = 1
					mat[4 * i + 3][4 * j] = 1
				elif grid[i][j] == '\\\\':
					mat[4 * i][4 * j] = 1
					mat[4 * i + 1][4 * j + 1] = 1
					mat[4 * i + 2][4 * j + 2] = 1
					mat[4 * i + 3][4 * j + 3] = 1
		dirs = [[-1, 0], [1, 0], [0, 1], [0, -1]]

		def dfs(i, j):
			visit[i][j] = 1
			for d in dirs:
				(x, y) = (i + d[0], j + d[1])
				if 0 <= x < 4 * m and 0 <= y < 4 * n and (not mat[x][y]):
					mat[x][y] = 1
					if not visit[x][y]:
						dfs(x, y)
		visit = [[0] * (4 * n) for _ in range(4 * m)]
		res = 0
		for i in range(4 * m):
			for j in range(4 * n):
				if not mat[i][j]:
					res += 1
					dfs(i, j)
		return res


class Solution:

	def regionsBySlashes(self, grid: List[str]) -> int:
		n = len(grid)
		seen = [[[0, 0, 0, 0] for x in range(n)] for y in range(n)]

		def dfs(x, y, loc):
			if not (0 <= x < n and 0 <= y < n) or seen[x][y][loc] == 1:
				return
			seen[x][y][loc] = 1
			if grid[x][y] == '/':
				if loc == 0:
					dfs(x + 1, y, 2)
					seen[x][y][3] = 1
					dfs(x, y + 1, 1)
				elif loc == 3:
					dfs(x, y + 1, 1)
					seen[x][y][0] = 1
					dfs(x + 1, y, 2)
				elif loc == 1:
					dfs(x, y - 1, 3)
					seen[x][y][2] = 1
					dfs(x - 1, y, 0)
				else:
					dfs(x - 1, y, 0)
					seen[x][y][1] = 1
					dfs(x, y - 1, 3)
			elif grid[x][y] == '\\\\':
				if loc == 0:
					dfs(x + 1, y, 2)
					seen[x][y][1] = 1
					dfs(x, y - 1, 3)
				elif loc == 3:
					dfs(x, y + 1, 1)
					seen[x][y][2] = 1
					dfs(x - 1, y, 0)
				elif loc == 1:
					dfs(x, y - 1, 3)
					seen[x][y][0] = 1
					dfs(x + 1, y, 2)
				else:
					dfs(x - 1, y, 0)
					seen[x][y][3] = 1
					dfs(x, y + 1, 1)
			else:
				seen[x][y][1] = 1
				dfs(x, y - 1, 3)
				seen[x][y][2] = 1
				dfs(x - 1, y, 0)
				seen[x][y][0] = 1
				dfs(x + 1, y, 2)
				seen[x][y][3] = 1
				dfs(x, y + 1, 1)
		count = 0
		for i in range(n):
			for j in range(n):
				for loc in range(4):
					k = seen[i][j][loc]
					if k == 0:
						count += 1
						dfs(i, j, loc)
		return count


class Solution:

	def regionsBySlashes(self, grid: List[str]) -> int:
		N = len(grid)
		base = N * (N + 1)
		parent = [i for i in range(2 * base)]

		def find(x):
			if parent[x] != parent[parent[x]]:
				parent[x] = find(parent[x])
			return parent[x]

		def union(x, y):
			parent[find(x)] = find(y)
			return find(y)
		for i in range(N):
			for j in range(N):
				(up, down, left, right) = (i * N + j, (i + 1) * N + j, base + i * (N + 1) + j, base + i * (N + 1) + j + 1)
				if grid[i][j] == '/':
					union(up, left)
					union(down, right)
				elif grid[i][j] == '\\\\':
					union(up, right)
					union(down, left)
				else:
					union(up, left)
					union(down, right)
					union(left, right)
		comp = set()
		for i in range(2 * base):
			comp.add(find(i))
		return len(comp)


class Solution:

	def regionsBySlashes(self, grid: List[str]):

		def minAnglePoint(p1, p2, options):
			minAngle = 10.0
			for p3 in options:
				a = (p2[0] - p1[0], p2[1] - p1[1])
				b = (p3[0] - p2[0], p3[1] - p2[1])
				dot = a[0] * b[0] + a[1] * b[1]
				det = a[0] * b[1] - a[1] * b[0]
				ang = math.atan2(det, dot)
				if ang < minAngle:
					minAngle = ang
					res = p3
			return (res, minAngle)
		N = len(grid)
		M = dict()
		for i in range(N):
			M[i + 1, 0] = [(i, 0)]
			M[N, i + 1] = [(N, i)]
			M[N - i - 1, N] = [(N - i, N)]
			M[0, N - i - 1] = [(0, N - i)]
		for y in range(N):
			x = 0
			for c in grid[y]:
				if c == '/':
					if (x + 1, y) in M:
						M[x + 1, y].append((x, y + 1))
					else:
						M[x + 1, y] = [(x, y + 1)]
					if (x, y + 1) in M:
						M[x, y + 1].append((x + 1, y))
					else:
						M[x, y + 1] = [(x + 1, y)]
				elif c == '\\\\':
					if (x, y) in M:
						M[x, y].append((x + 1, y + 1))
					else:
						M[x, y] = [(x + 1, y + 1)]
					if (x + 1, y + 1) in M:
						M[x + 1, y + 1].append((x, y))
					else:
						M[x + 1, y + 1] = [(x, y)]
				x += 1
		innerangle = round(-2 * math.pi, 4)
		points = sorted(M)
		regions = set()
		for i in range(len(points)):
			if points[i] not in M:
				continue
			startpoint = points[i]
			region = {startpoint}
			point = firststep = M[startpoint][0]
			M[startpoint].remove(point)
			prev = startpoint
			angSum = 0
			while point != startpoint:
				region.add(point)
				links = M[point]
				(nxt, ang) = minAnglePoint(prev, point, links)
				angSum += ang
				if len(links) == 1:
					del M[point]
				else:
					M[point].remove(nxt)
				prev = point
				point = nxt
			if len(M[startpoint]) == 0:
				del M[startpoint]
			(_, ang) = minAnglePoint(prev, point, [firststep])
			angSum = round(angSum + ang, 4)
			if angSum == innerangle:
				regions.add(frozenset(region))
		return len(regions)


class Solution:

	def regionsBySlashes(self, grid: List[str]) -> int:
		N = len(grid)
		new_grid = [[0] * (2 * N) for _ in range(2 * N)]
		count = 0
		for i in range(N):
			for j in range(N):
				if grid[i][j] == '/':
					new_grid[2 * i][2 * j + 1] = 1
					new_grid[2 * i + 1][2 * j] = 1
				elif grid[i][j] == '\\\\':
					new_grid[2 * i][2 * j] = 1
					new_grid[2 * i + 1][2 * j + 1] = 1

		def dfs(grid, i, j):
			if grid[i][j] == 1:
				return None
			grid[i][j] = 1
			if i < len(grid) - 1:
				dfs(grid, i + 1, j)
			if j < len(grid) - 1:
				dfs(grid, i, j + 1)
			if i > 0:
				dfs(grid, i - 1, j)
			if j > 0:
				dfs(grid, i, j - 1)
			if i < len(grid) - 1 and j > 0 and (i % 2 == j % 2):
				dfs(grid, i + 1, j - 1)
			if i > 0 and j < len(grid) - 1 and (i % 2 == j % 2):
				dfs(grid, i - 1, j + 1)
			if i < len(grid) - 1 and j < len(grid) - 1 and (i % 2 != j % 2):
				dfs(grid, i + 1, j + 1)
			if i > 0 and j > 0 and (i % 2 != j % 2):
				dfs(grid, i - 1, j - 1)
		for i in range(2 * N):
			for j in range(2 * N):
				if new_grid[i][j] == 0:
					count += 1
					dfs(new_grid, i, j)
		return count


class Solution:

	def regionsBySlashes(self, grid: List[str]) -> int:
		nrow = len(grid)
		ncol = len(grid[0])
		newgrid = []
		for i in range(nrow * 3):
			newgrid.append([0] * ncol * 3)
		for r in range(nrow):
			for c in range(ncol):
				if grid[r][c] == '\\\\':
					newgrid[r * 3][c * 3] = 1
					newgrid[r * 3 + 1][c * 3 + 1] = 1
					newgrid[r * 3 + 2][c * 3 + 2] = 1
				elif grid[r][c] == '/':
					newgrid[r * 3 + 2][c * 3] = 1
					newgrid[r * 3 + 1][c * 3 + 1] = 1
					newgrid[r * 3][c * 3 + 2] = 1

		def countIsland(newgrid):
			count = 0

			def dfs(r, c):
				if newgrid[r][c] == 0:
					newgrid[r][c] = 1
					if r < len(newgrid) - 1 and newgrid[r + 1][c] == 0:
						dfs(r + 1, c)
					if c < len(newgrid[0]) - 1 and newgrid[r][c + 1] == 0:
						dfs(r, c + 1)
					if r > 0 and newgrid[r - 1][c] == 0:
						dfs(r - 1, c)
					if c > 0 and newgrid[r][c - 1] == 0:
						dfs(r, c - 1)
			for r1 in range(len(newgrid)):
				for c1 in range(len(newgrid[0])):
					if newgrid[r1][c1] == 0:
						dfs(r1, c1)
						count += 1
					else:
						pass
			return count
		return countIsland(newgrid)


class Solution:

	def regionsBySlashes(self, grid: List[str]) -> int:
		N = len(grid)
		D = list(range(N * N * 4))
		res = [len(D)]

		def find(D, i):
			if D[i] == i:
				return i
			return find(D, D[i])

		def union(D, i, j):
			pi = find(D, i)
			pj = find(D, j)
			if pi == pj:
				return
			else:
				D[pi] = pj
				res[0] -= 1

		def idx(i, j, e):
			return (i * N + j) * 4 + e
		for i in range(N):
			for j in range(N):
				if i > 0:
					union(D, idx(i - 1, j, 2), idx(i, j, 0))
				if j > 0:
					union(D, idx(i, j - 1, 1), idx(i, j, 3))
				if grid[i][j] != '/':
					union(D, idx(i, j, 0), idx(i, j, 1))
					union(D, idx(i, j, 2), idx(i, j, 3))
				if grid[i][j] != '\\\\':
					union(D, idx(i, j, 0), idx(i, j, 3))
					union(D, idx(i, j, 1), idx(i, j, 2))
		return res[0]


class Solution:

	def regionsBySlashes(self, grid: List[str]) -> int:
		(m, n) = (len(grid), len(grid[0]))
		parent = {}

		def find(x):
			if parent[x] != x:
				parent[x] = find(parent[x])
			return parent[x]

		def union(x, y):
			(rx, ry) = (find(x), find(y))
			if rx == ry:
				return False
			parent[rx] = ry
			return True
		res = m * n * 4
		for i in range(m):
			for j in range(n):
				for k in range(4):
					parent[i, j, k] = (i, j, k)
				if grid[i][j] == '/':
					if union((i, j, 0), (i, j, 3)):
						res -= 1
					if union((i, j, 1), (i, j, 2)):
						res -= 1
				elif grid[i][j] == '\\\\':
					if union((i, j, 0), (i, j, 1)):
						res -= 1
					if union((i, j, 2), (i, j, 3)):
						res -= 1
				else:
					if union((i, j, 0), (i, j, 1)):
						res -= 1
					if union((i, j, 2), (i, j, 3)):
						res -= 1
					if union((i, j, 0), (i, j, 3)):
						res -= 1
				if i > 0:
					if union((i, j, 0), (i - 1, j, 2)):
						res -= 1
				if j > 0:
					if union((i, j, 3), (i, j - 1, 1)):
						res -= 1
		return res


class Solution:

	def regionsBySlashes(self, grid: List[str]) -> int:
		self.N = len(grid)
		print(self.N)
		pre = list(range(self.N * self.N * 4))
		self.count = self.N * self.N * 4
		for r in range(self.N):
			line = grid[r]
			for c in range(self.N):
				w = line[c]
				if r > 0:
					self.union(pre, self.g(r - 1, c, 2), self.g(r, c, 0))
				if c > 0:
					self.union(pre, self.g(r, c - 1, 1), self.g(r, c, 3))
				if w != '/':
					self.union(pre, self.g(r, c, 0), self.g(r, c, 1))
					self.union(pre, self.g(r, c, 3), self.g(r, c, 2))
				if w != '\\\\':
					self.union(pre, self.g(r, c, 0), self.g(r, c, 3))
					self.union(pre, self.g(r, c, 1), self.g(r, c, 2))
		return self.count

	def find(self, pre, x):
		if x == pre[x]:
			return x
		return self.find(pre, pre[x])

	def union(self, pre, a, b):
		pa = self.find(pre, a)
		pb = self.find(pre, b)
		if pa == pb:
			return
		pre[pa] = pb
		self.count -= 1

	def g(self, r, c, i):
		return (r * self.N + c) * 4 + i


class Solution:

	def regionsBySlashes(self, grid: List[str]) -> int:
		f = {}

		def find(x):
			if x not in f:
				f[x] = x
			elif f[x] != x:
				f[x] = find(f[x])
			return f[x]

		def merge(x, y):
			(rx, ry) = (find(x), find(y))
			f[rx] = ry
		(rows, cols) = (len(grid), len(grid[0]) if grid else 0)
		for i in range(rows):
			for j in range(cols):
				cur = (i * cols + j) * 4
				(up, left) = (((i - 1) * cols + j) * 4, (i * cols + j - 1) * 4)
				(cl, cr, cd) = (cur + 3, cur + 1, cur + 2)
				(lr, ud) = (left + 1, up + 2)
				if grid[i][j] == '/':
					merge(cur, cl)
					merge(cr, cd)
				elif grid[i][j] == '\\\\':
					merge(cur, cr)
					merge(cl, cd)
				else:
					merge(cur, cr)
					merge(cl, cd)
					merge(cur, cl)
				if i >= 1:
					merge(cur, ud)
				if j >= 1:
					merge(cl, lr)
		res = 0
		for i in range(rows):
			for j in range(cols):
				cur = (i * cols + j) * 4
				for dx in range(4):
					if cur + dx == find(cur + dx):
						res += 1
		return res


class UnionFind:

	def __init__(self, N):
		self.par = list(range(N))
		self.rank = [0] * N

	def find(self, x):
		if self.par[x] != x:
			self.par[x] = self.find(self.par[x])
		return self.par[x]

	def union(self, x, y):
		(px, py) = (self.find(x), self.find(y))
		if px == py:
			return
		if self.rank[px] < self.rank[py]:
			self.par[px] = py
		elif self.rank[px] > self.rank[py]:
			self.par[py] = px
		else:
			self.par[py] = px
			self.rank[px] += 1

class Solution:

	def regionsBySlashes(self, grid: List[str]) -> int:
		N = len(grid)
		uf = UnionFind(4 * N * N)
		for i in range(N):
			for j in range(N):
				idx = 4 * (i * N + j)
				if grid[i][j] != '/':
					uf.union(idx, idx + 1)
					uf.union(idx + 2, idx + 3)
				if grid[i][j] != '\\\\':
					uf.union(idx, idx + 3)
					uf.union(idx + 1, idx + 2)
				if i:
					uf.union(idx, idx - 4 * N + 2)
				if j:
					uf.union(idx + 3, idx - 4 + 1)
		return sum((uf.find(x) == x for x in range(4 * N * N)))


class Unionset:

	def __init__(self, N):
		self.parent = [x for x in range(N)]
		self.rank = [0 for x in range(N)]

	def find(self, x):
		if self.parent[x] != x:
			self.parent[x] = self.find(self.parent[x])
		return self.parent[x]

	def union(self, x, y):
		xx = self.find(x)
		yy = self.find(y)
		if self.parent[xx] == self.parent[yy]:
			return True
		if self.rank[xx] > self.rank[yy]:
			self.parent[yy] = self.parent[xx]
		elif self.rank[xx] < self.rank[yy]:
			self.parent[xx] = self.parent[yy]
		else:
			self.rank[xx] += 1
			self.parent[yy] = self.parent[xx]
		return False

class Solution:

	def regionsBySlashes(self, grid: List[str]) -> int:
		n = len(grid)
		ds = Unionset(n * n * 4)
		for r in range(n):
			for c in range(n):
				root = 4 * (r * n + c)
				if grid[r][c] == '/':
					ds.union(root, root + 1)
					ds.union(root + 2, root + 3)
				elif grid[r][c] == '\\\\':
					ds.union(root, root + 2)
					ds.union(root + 1, root + 3)
				else:
					ds.union(root, root + 1)
					ds.union(root + 1, root + 2)
					ds.union(root + 2, root + 3)
				if r + 1 < n:
					ds.union(root + 3, root + 4 * n)
				if c + 1 < n:
					ds.union(root + 2, root + 5)
		tot = 0
		for i in range(4 * n * n):
			if ds.find(i) == i:
				tot += 1
		return tot


class DSU:

	def __init__(self, N):
		self.pres = list(range(N))

	def setRoot(self, i, root):
		while self.pres[i] != root:
			t = self.pres[i]
			self.pres[i] = root
			i = t
		return

	def findRoot(self, i):
		root = i
		while root != self.pres[root]:
			root = self.pres[root]
		self.setRoot(i, root)
		return root

	def merge(self, i, j):
		root = self.findRoot(i)
		self.setRoot(j, root)

class Solution:

	def regionsBySlashes(self, grid: List[str]) -> int:

		def getPos(N, h, w, i):
			return N * 4 * h + 4 * w + i
		N = len(grid)
		NN4 = N * N * 4
		dsu = DSU(NN4)
		for h in range(N):
			for w in range(N):
				p = getPos(N, h, w, 0)
				pR = getPos(N, h, w + 1, 0)
				pD = getPos(N, h + 1, w, 0)
				pRD = getPos(N, h + 1, w + 1, 0)
				if h < N - 1:
					dsu.merge(p + 2, pD + 0)
				if w < N - 1:
					dsu.merge(p + 1, pR + 3)
		for h in range(N):
			for w in range(N):
				p = getPos(N, h, w, 0)
				if grid[h][w] == '/':
					dsu.merge(p + 0, p + 3)
					dsu.merge(p + 1, p + 2)
				elif grid[h][w] == '\\\\':
					dsu.merge(p + 0, p + 1)
					dsu.merge(p + 2, p + 3)
				else:
					dsu.merge(p + 0, p + 1)
					dsu.merge(p + 0, p + 2)
					dsu.merge(p + 0, p + 3)
		return sum((dsu.findRoot(x) == x for x in range(NN4)))


class Solution:

	def regionsBySlashes(self, grid):
		n = len(grid)
		g = [[0 for _ in range(n * 3)] for _ in range(n * 3)]

		def dfs(i, j):
			if 0 <= i < n * 3 and 0 <= j < n * 3 and (g[i][j] == 0):
				g[i][j] = 1
				for k in [1, -1]:
					dfs(i + k, j)
					dfs(i, j + k)
		for i in range(n):
			for j in range(n):
				if grid[i][j] == '/':
					g[i * 3][j * 3 + 2] = 1
					g[i * 3 + 1][j * 3 + 1] = 1
					g[i * 3 + 2][j * 3] = 1
				elif grid[i][j] == '\\\\':
					g[i * 3][j * 3] = 1
					g[i * 3 + 1][j * 3 + 1] = 1
					g[i * 3 + 2][j * 3 + 2] = 1
		res = 0
		for i in range(n * 3):
			for j in range(n * 3):
				if g[i][j] == 0:
					dfs(i, j)
					res += 1
		return res


class Solution:

	def regionsBySlashes(self, g: List[str]) -> int:
		n = len(g)
		grid = [[0] * (n * 3) for j in range(n * 3)]
		for i in range(n):
			for j in range(n):
				if g[i][j] == '/':
					grid[i * 3][j * 3 + 2] = 1
					grid[i * 3 + 1][j * 3 + 1] = 1
					grid[i * 3 + 2][j * 3] = 1
				elif g[i][j] == '\\\\':
					grid[i * 3][j * 3] = 1
					grid[i * 3 + 1][j * 3 + 1] = 1
					grid[i * 3 + 2][j * 3 + 2] = 1

		def dfs(i, j):
			grid[i][j] = 1
			for r in [(i + 1, j), (i, j + 1), (i - 1, j), (i, j - 1)]:
				(xx, yy) = r
				if xx < 0 or yy < 0 or xx >= len(grid) or (yy >= len(grid[0])) or (grid[xx][yy] == 1):
					continue
				dfs(xx, yy)
		count = 0
		for i in range(n * 3):
			for j in range(n * 3):
				if grid[i][j] == 0:
					dfs(i, j)
					count += 1
		return count


class Solution:

	def regionsBySlashes(self, grid: List[str]) -> int:
		if not grid:
			return 0
		(rows, cols) = (len(grid), len(grid[0]))
		new_grid = [[0] * 3 * cols for _ in range(3 * rows)]
		visited = [[False] * 3 * cols for _ in range(3 * rows)]
		for i in range(rows):
			line = grid[i]
			for j in range(len(line)):
				if line[j] == '/':
					new_grid[3 * i][3 * j + 2] = 1
					new_grid[3 * i + 1][3 * j + 1] = 1
					new_grid[3 * i + 2][3 * j] = 1
				elif line[j] == '\\\\':
					new_grid[3 * i][3 * j] = 1
					new_grid[3 * i + 1][3 * j + 1] = 1
					new_grid[3 * i + 2][3 * j + 2] = 1

		def dfs(i, j):
			if i < 0 or j < 0 or i >= 3 * rows or (j >= 3 * cols) or (new_grid[i][j] == 1) or visited[i][j]:
				return
			visited[i][j] = True
			dfs(i, j + 1)
			dfs(i + 1, j)
			dfs(i, j - 1)
			dfs(i - 1, j)
		count = 0
		for i in range(3 * rows):
			for j in range(3 * cols):
				if not visited[i][j] and new_grid[i][j] == 0:
					dfs(i, j)
					count += 1
		return count


class Solution:

	def regionsBySlashes(self, grid: List[str]) -> int:
		n = len(grid)
		(m, ans) = ([[[0, 0, 0, 0] for j in range(n)] for i in range(n)], 0)

		def dfs(i, j, k):
			if 0 <= i < n and 0 <= j < n and (not m[i][j][k]):
				if grid[i][j] == '/':
					if 1 <= k <= 2:
						m[i][j][1] = m[i][j][2] = ans
						dfs(i, j + 1, 3)
						dfs(i + 1, j, 0)
					else:
						m[i][j][0] = m[i][j][3] = ans
						dfs(i - 1, j, 2)
						dfs(i, j - 1, 1)
				elif grid[i][j] == '\\\\':
					if k <= 1:
						m[i][j][0] = m[i][j][1] = ans
						dfs(i - 1, j, 2)
						dfs(i, j + 1, 3)
					else:
						m[i][j][2] = m[i][j][3] = ans
						dfs(i + 1, j, 0)
						dfs(i, j - 1, 1)
				else:
					m[i][j][0] = m[i][j][1] = m[i][j][2] = m[i][j][3] = ans
					dfs(i - 1, j, 2)
					dfs(i, j - 1, 1)
					dfs(i + 1, j, 0)
					dfs(i, j + 1, 3)
		for i in range(n):
			for j in range(n):
				for k in range(4):
					if not m[i][j][k]:
						ans += 1
						dfs(i, j, k)
		return ans


class Solution:

	def regionsBySlashes(self, grid: List[str]) -> int:
		if len(grid) == 0 or len(grid[0]) == 0:
			return 0
		roots = {}

		def find(x):
			roots.setdefault(x, x)
			if roots[x] != x:
				roots[x] = find(roots[x])
			return roots[x]

		def union(x, y):
			roots[find(x)] = find(y)
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if i > 0:
					union((i - 1, j, 2), (i, j, 0))
				if j > 0:
					union((i, j - 1, 1), (i, j, 3))
				if grid[i][j] != '/':
					union((i, j, 0), (i, j, 1))
					union((i, j, 2), (i, j, 3))
				if grid[i][j] != '\\\\':
					union((i, j, 0), (i, j, 3))
					union((i, j, 1), (i, j, 2))
		return len(set((find(x) for x in list(roots.keys()))))


class Solution:

	def regionsBySlashes(self, grid: List[str]) -> int:
		root = {}

		def find(x):
			root.setdefault(x, x)
			if root[x] != x:
				root[x] = find(root[x])
			return root[x]

		def union(x, y):
			(rx, ry) = (find(x), find(y))
			if rx != ry:
				root[ry] = find(rx)
		for i in range(len(grid)):
			for j in range(len(grid)):
				if i:
					union((i - 1, j, 2), (i, j, 0))
				if j:
					union((i, j - 1, 1), (i, j, 3))
				if grid[i][j] == '/':
					union((i, j, 0), (i, j, 3))
					union((i, j, 1), (i, j, 2))
				elif grid[i][j] == '\\\\':
					union((i, j, 0), (i, j, 1))
					union((i, j, 2), (i, j, 3))
				else:
					union((i, j, 0), (i, j, 1))
					union((i, j, 0), (i, j, 2))
					union((i, j, 0), (i, j, 3))
		return len(set(map(find, list(root.keys()))))