leetcode困难题（leetcode959go由斜杠划分区域）
在由 1 x 1 方格组成的 N x N 网格 grid 中，每个 1 x 1 方块由 /、\ 或空格构成。这些字符会将方块划分为一些共边的区域。
（请注意，反斜杠字符是转义的，因此 \ 用 "\\" 表示。）。
返回区域的数目。
示例 1：输入：
[
" /",
"/ "
]
输出：2
解释：2x2 网格如下：
示例 2：输入：
[
" /",
" "
]
输出：1
解释：2x2 网格如下：
示例 3：输入：
[
"\\/",
"/\\"
]
输出：4
解释：（回想一下，因为 \ 字符是转义的，所以 "\\/" 表示 \/，而 "/\\" 表示 /\。）
2x2 网格如下：
示例 4：输入：
[
"/\\",
"\\/"
]
输出：5
解释：（回想一下，因为 \ 字符是转义的，所以 "/\\" 表示 /\，而 "\\/" 表示 \/。）
2x2 网格如下：
示例 5：输入：
[
"//",
"/ "
]
输出：3
解释：2x2 网格如下：
提示：1 <= grid.length == grid[0].length <= 30
grid[i][j] 是 '/'、'\'、或 ' '。
解题思路分析1、并查集；时间复杂度O(n^2log(n))，空间复杂度O(n^2)
func regionsBySlashes(grid []string) int {
n := len(grid)
fa = Init(n * n * 4)
for i := 0; i < n; i {
for j := 0; j < n; j {
index := 4 * (i*n j) // 扩大4倍，每个格子拆分为4个：0、1、2、3（顺时针）
if grid[i][j] == '/' {
union(index, index 3) // 合并0、3
union(index 1, index 2) // 合并1、2
} else if grid[i][j] == '\\' {
union(index, index 1) // 合并0、1
union(index 2, index 3) // 合并2、3
} else {
union(index, index 1) // 合并0、1、2、3
union(index 1, index 2)
union(index 2, index 3)
}
if j < n-1 {
union(index 1, index 7) // 向右合并
}
if i < n-1 {
union(index 2, index 4*n) // 向下合并
}
}
}
return getCount()
}
var fa []int
var count int
// 初始化
func Init(n int) []int {
arr := make([]int, n)
for i := 0; i < n; i {
arr[i] = i
}
count = n
return arr
}
// 查询
func find(x int) int {
if fa[x] == x {
return x
}
// 路径压缩
fa[x] = find(fa[x])
return fa[x]
}
// 合并
func union(i, j int) {
x, y := find(i), find(j)
if x != y {
fa[x] = y
count--
}
}
func query(i, j int) bool {
return find(i) == find(j)
}
func getCount() int {
return count
}
2、深度优先搜索；时间复杂度O(n^2)，空间复杂度O(n^2)
func regionsBySlashes(grid []string) int {
n := len(grid)
arr := make([][]int, 3*n)
for i := 0; i < 3*n; i {
arr[i] = make([]int, 3*n)
}
for i := 0; i < n; i { // 放大处理
for j := 0; j < n; j {
if grid[i][j] == '/' { // 9宫格
arr[i*3 2][j*3] = 1
arr[i*3 1][j*3 1] = 1
arr[i*3][j*3 2] = 1
} else if grid[i][j] == '\\' {
arr[i*3 2][j*3 2] = 1
arr[i*3 1][j*3 1] = 1
arr[i*3][j*3] = 1
}
}
}
res := 0
for i := 0; i < 3*n; i {
for j := 0; j < 3*n; j {
if arr[i][j] == 0 {
dfs(arr, i, j)
res
}
}
}
return res
}
func dfs(arr [][]int, i, j int) {
if 0 <= i && i < len(arr) && 0 <= j && j < len(arr[0]) && arr[i][j] == 0 {
arr[i][j] = 1
dfs(arr, i 1, j)
dfs(arr, i-1, j)
dfs(arr, i, j-1)
dfs(arr, i, j 1)
}
}
Medium题目，简单一些思路就是进行放大处理，把单个字符转换为9宫格，然后题目就变成 leetcode 200.岛屿数量
,免责声明：本文仅代表文章作者的个人观点，与本站无关。其原创性、真实性以及文中陈述文字和内容未经本站证实，对本文以及其中全部或者部分内容文字的真实性、完整性和原创性本站不作任何保证或承诺，请读者仅作参考，并自行核实相关内容。文章投诉邮箱：anhduc.ph@yahoo.com
