0959：由斜杠划分区域（2135 分）

2018-12-16 约 407 字预计阅读 1 分钟次阅读

力扣第 115 场周赛第 3 题

题目

在由 1 x 1 方格组成的 n x n 网格 grid 中，每个 1 x 1 方块由 '/'、'\' 或空格构成。这些字符会将方块划分为一些共边的区域。

给定网格 grid 表示为一个字符串数组，返回 区域的数量 。

请注意，反斜杠字符是转义的，因此 '\' 用 '\\' 表示。

示例 1：

输入：grid = [" /","/ "]
输出：2

示例 2：

输入：grid = [" /","  "]
输出：1

示例 3：

输入：grid = ["/\\","\\/"]
输出：5
解释：回想一下，因为 \ 字符是转义的，所以 "/\\" 表示 /\，而 "\\/" 表示 \/。

提示：

n == grid.length == grid[i].length
1 <= n <= 30
grid[i][j] 是 '/'、'\'、或 ' '

分析

区域数量其实就是连通块的数量，考虑用并查集
注意 ‘/’ 和 ‘' 将方格分为四小块，因此考虑对每一小块遍历并连通
注意方格 (i, j) 左小块和 (i, j-1) 右小块必然连通，方格 (i, j) 上小块和 (i-1, j) 下小块必然连通

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


class Solution:
    def regionsBySlashes(self, grid: List[str]) -> int:
        def find(x):
            if f[x]!=x:
                f[x]=find(f[x])
            return f[x]
        
        def union(x,y):
            f[find(x)]=find(y)

        n = len(grid)
        f = list(range(n*n*4))
        for i in range(n):
            for j in range(n):
                base = i*n*4+j*4
                if i:
                    union(base,base-n*4+2)
                if j:
                    union(base+3,base-3)
                x = grid[i][j]
                if x!='/':
                    union(base,base+1)
                    union(base+2,base+3)
                if x!='\\':
                    union(base+1,base+2)
                    union(base,base+3)
        return sum(find(i)==i for i in range(n*n*4))

81 ms

目录

0959：由斜杠划分区域（2135 分）

题目

分析

解答