959. 由斜杠划分区域【并查集】

题目

在由 1 x 1 方格组成的 N x N 网格 grid 中，每个 1 x 1 方块由 /、\ 或空格构成。这些字符会将方块划分为一些共边的区域。
（请注意，反斜杠字符是转义的，因此 \ 用 "\" 表示。）。
返回区域的数目。

示例 1：
输入：
[
" /",
"/ "
]
输出：2
解释：2x2 网格如下：

示例1

示例 2：
输入：
[
" /",
" "
]
输出：1
解释：2x2 网格如下：

示例2

示例 3：
输入：
[
"\/",
"/\"
]
输出：4
解释：（回想一下，因为 \ 字符是转义的，所以 "\/" 表示 /，而 "/\" 表示 /\。）
2x2 网格如下：

示例3

示例 4：
输入：
[
"/\",
"\/"
]
输出：5
解释：（回想一下，因为 \ 字符是转义的，所以 "/\" 表示 /\，而 "\/" 表示 /。）
2x2 网格如下：

示例4

示例 5：
输入：
[
"//",
"/ "
]
输出：3
解释：2x2 网格如下：

示例5

提示：
1 <= grid.length == grid[0].length <= 30
grid[i][j] 是 '/'、''、或 ' '。

思路

思路

1、将每个小格子使用 / \ 画分成上面的四个小区域，依次编号0、1、2、3；
2、按输入情况，合并4个小格子：
（1）如果输入的是' '（空格），则将0、1、2、3合并；
（2）如果输入的是'/'，则将0、3合并，1、2合并；
（3）如果输入的是'\'（\需要转义），则将0、1合并，2、3合并；
3、与周边大格子进行合并，不管该格子输入的是什么：
（1）如果不是第1行，该格子的0一定与上1行格子的2合并（连通的）；
（2）如果不是最后1行，该格子的2一定与下1行的0合并；
（3）如果不是第1列，该格子的3一定与左边1列的1合并；
（4）如果不是最后1列，该格子的1一定与右边1列的3合并；

并查集的实现

// 实现一个并查集
type UnionFindSet struct {
    Parent []int             // 下标i的值是自己，parent[i]的值指向自己的主人(集合标号)
}

// 创建一个元素个数为n的并查集
func NewUionFindSet(n int) *UnionFindSet {
    ufs := &UnionFindSet{Parent: make([]int, n, n),}
    for i:=0; i<n; i++ {
        ufs.Parent[i] = i    // 开始时，每个元素都是一个集合
    }
    return ufs
}

// find，查找元素i的主人，并在此过程中，将自己主人的值为最顶层的主人
func(ufs *UnionFindSet) Find(x int) int {
    if ufs.Parent[x] != x {                           // 自己不是自己的主人
        ufs.Parent[x] = ufs.Find(ufs.Parent[x])       // 找自己主人的主人
    }

    return ufs.Parent[x]                              // 最顶层的主人，自己的主人是自己
}

// union： 合并元素x和元素y
func(ufs *UnionFindSet) Union(x, y int) {
    ufs.Parent[ufs.Find(x)] = ufs.Find(y)             // x的主人的父亲，是y的主人
}

解题代码

//     0
//  3     1
//     2
func regionsBySlashes(grid []string) int {
    N := len(grid)                    // N*N个格子
    ufs := NewUionFindSet(4*N*N)      // 每个格子分成4个小格子

    for row := 0; row < N; row ++ {       // 行
        for col := 0; col < N; col ++ {   // 列
            root := 4*(row*N+col)         // 每个格子0所在的位置

            // 合并每个格子
            // 1
            if grid[row][col] == ' ' {
                ufs.Union(root, root+1)
                ufs.Union(root, root+2)
                ufs.Union(root, root+3)
            }

            // 2
            if grid[row][col] == '\\' {
                ufs.Union(root, root+1)
                ufs.Union(root+2, root+3)
            }

            // 3
            if grid[row][col] == '/' {
                ufs.Union(root, root+3)
                ufs.Union(root+1, root+2)
            }

            // 与周边格子合并，上下左右
            // 如果不是最后1行，本格子的2和下一行盒子的0合并
            if row + 1 < N {
                ufs.Union(root+2, root + 4*N)
            }

            // 如果不是第1行，本格子的0和上一行盒子的2合并
            if row - 1 >= 0 {
                ufs.Union(root, root + 2 - 4*N)
            }

            // 如果不是最后1列，本格子的1和右1列的3合并
            if col + 1 < N {
                ufs.Union(root + 1, root + 3 + 4)
            }

            // 如果不是第1列，本格子的3和左1列的1合并
            if col - 1 >= 0 {
                ufs.Union(root + 3, root + 1 - 4)
            }
        }
    }

    // 获得答案
    var ans int
    for i:=0; i<4*N*N; i++ {
        if ufs.Find(i) == i {   // 统计集合个数
            ans ++
        }
    }

    return ans
}