题目
在由 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
}
网友评论