-
Notifications
You must be signed in to change notification settings - Fork 521
/
c.go
76 lines (74 loc) · 1.06 KB
/
c.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
package main
// github.com/EndlessCheng/codeforces-go
func regionsBySlashes(a []string) (ans int) {
n := len(a)
m := n * n
g := make([][]int, 2*m)
add := func(v, w int) {
g[v] = append(g[v], w)
g[w] = append(g[w], v)
}
for i, r := range a {
for j, b := range r {
v := i*n + j
w := v + m
if i > 0 {
add(v, w-n)
}
if i < n-1 {
add(w, v+n)
}
if b == '/' {
if j > 0 {
if r[j-1] == '/' {
add(v, w-1)
} else {
add(v, v-1)
}
}
if j < n-1 {
if r[j+1] == '/' {
add(w, v+1)
} else {
add(w, w+1)
}
}
} else {
if b == ' ' {
add(v, w)
}
if j > 0 {
if r[j-1] == '/' {
add(w, w-1)
} else {
add(w, v-1)
}
}
if j < n-1 {
if r[j+1] == '/' {
add(v, v+1)
} else {
add(v, w+1)
}
}
}
}
}
vis := make([]bool, len(g))
var f func(int)
f = func(v int) {
vis[v] = true
for _, w := range g[v] {
if !vis[w] {
f(w)
}
}
}
for i, b := range vis {
if !b {
ans++
f(i)
}
}
return
}