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 ' '.

Difficulty: interview

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)]
        #visited = set()
        #print(grid)
        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

        # dirs = [(0, 1), (-1, 0)]
        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
        # print(mat)
        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)]
        # top 1, left 2, bottom 3, right 0
        def dfs(x, y, loc):
            #print(x,y)
            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:
                        #print(i,j,k, seen)
                        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     # a ridiculously big number
            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: # it is a valid region
                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):
            # starting with a seed (0 in location i,j), build up an open space
            if grid[i][j] == 1:
                return None
            grid[i][j] = 1 # mark as visited
            if i < len(grid)-1: # (make sure i+1 exists)
                dfs(grid, i+1, j) # search down 
            if j < len(grid)-1: 
                dfs(grid, i, j+1)# search right
            if i > 0:
                dfs(grid, i-1, j) # search up
            if j > 0:
                dfs(grid, i, j-1) #search left
            # search dl
            if i < len(grid)-1 and j > 0 and i%2==j%2:
                dfs(grid, i+1, j-1)
            # search ur
            if i > 0 and j < len(grid)-1 and i%2==j%2:
                dfs(grid, i-1, j+1)
            # search dr
            if i < len(grid)-1 and j < len(grid)-1 and i%2!=j%2:
                dfs(grid, i+1, j+1)
            # search ul
            if i > 0 and j > 0 and i%2!=j%2:
                dfs(grid, i-1, j-1)
        
        # search for seeds (new islands)
        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) # seed an island
        
        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)#n行
        print((self.N))
        pre = list(range(self.N*self.N*4))#所有元素自己是自己的父节点[0,1,2,3,4,5,6,...]
        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)
        # print(uf.par)
        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)
        #print(ds.parent)
        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)
                #print(grid[r][c])
                #print(\"first\",ds.parent)
                if r+1<n:
                    ds.union(root+3,root+(4*n))
                if c+1<n:
                    ds.union(root+2,root+5)
                #print(\"second\",ds.parent)
        tot=0
        for i in range(4*n*n):
            if ds.find(i)==i:
                tot+=1
        return tot


#
# *-------*
# | \\ 0 / |
# | 3 * 1 |
# | / 2 \\ |
# *-------*
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: 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):
            # starting with a seed (0 in location i,j), build up an open space
            if grid[i][j] == 1:
                return None
            grid[i][j] = 1 # mark as visited
            if i < len(grid)-1: # (make sure i+1 exists)
                dfs(grid, i+1, j) # search down 
            if j < len(grid)-1: 
                dfs(grid, i, j+1)# search right
            if i > 0:
                dfs(grid, i-1, j) # search up
            if j > 0:
                dfs(grid, i, j-1) #search left
            # search dl
            if i < len(grid)-1 and j > 0 and i%2==j%2:
                dfs(grid, i+1, j-1)
            # search ur
            if i > 0 and j < len(grid)-1 and i%2==j%2:
                dfs(grid, i-1, j+1)
            # search dr
            if i < len(grid)-1 and j < len(grid)-1 and i%2!=j%2:
                dfs(grid, i+1, j+1)
            # search ul
            if i > 0 and j > 0 and i%2!=j%2:
                dfs(grid, i-1, j-1)
            
            
            
        
        # search for seeds
        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) # seed an island
        
        return count
                    
            


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)
        
        # k=0 top
        # k=1 right
        # k=2 bottom
        # k=3 left
        
        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:
        
        N = len(grid)
        
        matrix = 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 sum(find(x)[0] == x for x in range(4 * N * N))
                        


class Solution:
    def regionsBySlashes(self, grid: List[str]) -> int:
        
        root = {}
        
        def find(x):
            root.setdefault(x, x)
            if root[x] != x:  # not find( root[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())) ) )
                
        


from itertools import chain
class Solution:
    def regionsBySlashes(self, grid):
        grid = convert_grid(grid)
        return len([destroy_island(x, y, grid) for y in range(len(grid)) for x,v in enumerate(grid[y]) if v == 0])

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

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 grid[y + d_y][x] != sep or 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))))

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

from itertools import chain
class Solution:
    def regionsBySlashes(self, grid):
        grid = convert_grid(grid)
        return len([destroy_island(x, y, grid) for y in range(len(grid)) for x,v in enumerate(grid[y]) if v == 0])

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

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))))

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

from itertools import chain
class Solution:
    def regionsBySlashes(self, grid):
        grid = convert_grid(grid)
        print(*(list(map(str, x)) for x in grid), sep='\
')
        return len([destroy_island(x, y, grid) for y in range(len(grid)) for x,v in enumerate(grid[y]) if v == 0])

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

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 grid[y + d_y][x] != sep or 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))))

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