959. Regions Cut By Slashes
給n*n的grid
每一格可能包含3種元素'\'、'/'、' '
請問這個grid裡會有幾個area
思路:
把每一格變成3*3的pixel
'/' = [0,0,1
0,1,0
1,0,0]
像這樣
然後再去算總共分了幾個區域
等下來看看union find要怎麼做
golang code :
func regionsBySlashes(grid []string) int {
n := len(grid)
pixel := make([][]bool, 3*n)
for i := 0; i < 3*n; i++ {
pixel[i] = make([]bool, 3*n)
}
draw := func(i, j int, input byte) {
x, y := i*3, j*3
if input == '/' {
pixel[x][y+2] = true
pixel[x+1][y+1] = true
pixel[x+2][y] = true
} else if input == '\\' {
pixel[x][y] = true
pixel[x+1][y+1] = true
pixel[x+2][y+2] = true
}
}
for i, val := range grid {
for j := 0; j < len(val); j++ {
draw(i, j, val[j])
}
}
m, Ans := 3*n, 0
for i := 0; i < m; i++ {
for j := 0; j < m; j++ {
if !pixel[i][j] {
region_cnt(pixel, i, j)
Ans++
}
}
}
return Ans
}
func region_cnt(pixel [][]bool, i, j int) {
n := len(pixel)
if i < n && j < n && i > -1 && j > -1 && !pixel[i][j] {
pixel[i][j] = true
region_cnt(pixel, i+1, j)
region_cnt(pixel, i, j+1)
region_cnt(pixel, i-1, j)
region_cnt(pixel, i, j-1)
}
}