-
Notifications
You must be signed in to change notification settings - Fork 502
/
d.go
92 lines (89 loc) · 1.46 KB
/
d.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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
package main
// github.com/EndlessCheng/codeforces-go
func isPrintable(a [][]int) (ans bool) {
var mix, miy, mxx, mxy [61]int
for i := 1; i < 61; i++ {
mix[i] = 99
miy[i] = 99
}
for i, row := range a {
for j, v := range row {
mix[v] = min(mix[v], i)
miy[v] = min(miy[v], j)
mxx[v] = max(mxx[v], i)
mxy[v] = max(mxy[v], j)
}
}
g := [61][]int{}
deg := [61]int{-1}
for v := 1; v < 60; v++ {
if mix[v] == 99 {
continue
}
for w := v + 1; w < 61; w++ {
if mix[w] == 99 {
continue
}
up, down, l, r := max(mix[v], mix[w]), min(mxx[v], mxx[w]), max(miy[v], miy[w]), min(mxy[v], mxy[w])
if up > down || l > r {
continue
}
hasV, hasW := false, false
for _, row := range a[up : down+1] {
for _, x := range row[l : r+1] {
if x == v {
if hasW {
return
}
hasV = true
} else if x == w {
if hasV {
return
}
hasW = true
}
}
}
if hasV {
g[w] = append(g[w], v)
deg[v]++
} else if hasW {
g[v] = append(g[v], w)
deg[w]++
}
}
}
q := []int{}
for i, d := range deg[:] {
if d == 0 {
q = append(q, i)
}
}
for len(q) > 0 {
v := q[0]
q = q[1:]
for _, w := range g[v] {
if deg[w]--; deg[w] == 0 {
q = append(q, w)
}
}
}
for _, d := range deg[1:] {
if d > 0 {
return
}
}
return true
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
func max(a, b int) int {
if a > b {
return a
}
return b
}