0959. Regions Cut by Slashes

# 959. Regions Cut By Slashes#

## 题目 #

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. `1 <= grid.length == grid[0].length <= 30`
2. `grid[i][j]` is either `'/'``'\'`, or `' '`.

## 题目大意 #

• 1 <= grid.length == grid[0].length <= 30
• grid[i][j] 是 ‘/'、''、或 ' ‘。

## 解题思路 #

• 给出一个字符串，代表的是 `N x N` 正方形中切分的情况，有 2 种切分的情况 `'\'``'/'` ，即从左上往右下切和从右上往左下切。问按照给出的切分方法，能把 `N x N` 正方形切成几部分？
• 这一题解题思路是并查集。先将每个 `1*1` 的正方形切分成下图的样子。分成 4 小块。然后按照题目给的切分图来合并各个小块。

• 遇到 `'\\'`，就把第 0 块和第 1 块 `union()` 起来，第 2 块和第 3 块 `union()` 起来；遇到 `'/'`，就把第 0 块和第 3 块 `union()` 起来，第 2 块和第 1 块 `union()` 起来；遇到 `' '`，就把第 0 块和第 1 块 `union()` 起来，第 2 块和第 1 块 `union()` 起来，第 2 块和第 3 块 `union()` 起来，即 4 块都 `union()` 起来；最后还需要记得上一行和下一行还需要 `union()`，即本行的第 2 块和下一行的第 0 块 `union()` 起来；左边一列和右边一列也需要 `union()`。即本列的第 1 块和右边一列的第 3 块 `union()` 起来。最后计算出集合总个数就是最终答案了。

## 代码 #

``````
package leetcode

import (
"github.com/halfrost/leetcode-go/template"
)

func regionsBySlashes(grid []string) int {
size := len(grid)
uf := template.UnionFind{}
uf.Init(4 * size * size)
for i := 0; i < size; i++ {
for j := 0; j < size; j++ {
switch grid[i][j] {
case '\\':
uf.Union(getFaceIdx(size, i, j, 0), getFaceIdx(size, i, j, 1))
uf.Union(getFaceIdx(size, i, j, 2), getFaceIdx(size, i, j, 3))
case '/':
uf.Union(getFaceIdx(size, i, j, 0), getFaceIdx(size, i, j, 3))
uf.Union(getFaceIdx(size, i, j, 2), getFaceIdx(size, i, j, 1))
case ' ':
uf.Union(getFaceIdx(size, i, j, 0), getFaceIdx(size, i, j, 1))
uf.Union(getFaceIdx(size, i, j, 2), getFaceIdx(size, i, j, 1))
uf.Union(getFaceIdx(size, i, j, 2), getFaceIdx(size, i, j, 3))
}
if i < size-1 {
uf.Union(getFaceIdx(size, i, j, 2), getFaceIdx(size, i+1, j, 0))
}
if j < size-1 {
uf.Union(getFaceIdx(size, i, j, 1), getFaceIdx(size, i, j+1, 3))
}
}
}
count := 0
for i := 0; i < 4*size*size; i++ {
if uf.Find(i) == i {
count++
}
}
return count
}

func getFaceIdx(size, i, j, k int) int {
return 4*(i*size+j) + k
}

``````

Apr 8, 2023