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) } } -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.137.51.54 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1723261724.A.F96.html