1.25打卡

959. 由斜杠划分区域

今天的题，依旧并查集

更多的例子

做法

计算并查集连通分量,借leetcode大佬的图

下面是代码（py）

class Solution:
    def regionsBySlashes(self, grid: List[str]) -> int:
        N=len(grid)
        parent=[i for i in range(4*N*N)]
        def find(node):#递归寻找根节点
            if parent[node] != node:
                parent[node] = find(parent[node])
            return parent[node]
        def union(a,b):#链接节点
            root_a,root_b = find(a),find(b)
            if root_a != root_b:
                parent[root_a] = root_b
        for r in range(N):
            for c in range(N):
                base = 4 * (r * N + c)#当前第一个的编号
                char=grid[r][c]
                if char == '\\':
                    union(base+0,base+3)
                    union(base+1,base+2)
                elif char=='/':
                    union(base+0,base+1)
                    union(base+2,base+3)
                else:
                    union(base+0,base+1)
                    union(base+2,base+3)
                    union(base+0,base+2)
                if c < N-1:
                    union(base+2,base+4)
                if r < N-1:
                    union(base+3,base+4*N+1)
        return sum(parent[i] == i for i in range(4*N*N))