For problem statement at 1000-1999/1200-1299/1280-1289/1284/problemG.txt this is a correct solution, but verifier at 1000-1999/1200-1299/1280-1289/1284/verifierG.go ends with can you fix the verifier? package main
import (
"bufio"
"fmt"
"os"
)
type Edge struct {
id int
B int
W int
}
type AdjEdge struct {
to int
edgeIdx int
}
func main() {
reader := bufio.NewReader(os.Stdin)
writer := bufio.NewWriter(os.Stdout)
defer writer.Flush()
var t int
if _, err := fmt.Fscan(reader, &t); err != nil {
return
}
for tc := 0; tc < t; tc++ {
var n, m int
fmt.Fscan(reader, &n, &m)
grid := make([]string, n)
for i := 0; i < n; i++ {
fmt.Fscan(reader, &grid[i])
}
cellID := make([][]int, n)
for i := range cellID {
cellID[i] = make([]int, m)
for j := range cellID[i] {
cellID[i][j] = -1
}
}
V := 0
r_id := -1
var isBlack []bool
for i := 0; i < n; i++ {
for j := 0; j < m; j++ {
if grid[i][j] == 'O' {
cellID[i][j] = V
if i == 0 && j == 0 {
r_id = V
}
if (i+j)%2 == 0 {
isBlack = append(isBlack, true)
} else {
isBlack = append(isBlack, false)
}
V++
}
}
}
edges := []Edge{}
adjList := make([][]AdjEdge, V)
edgeCount := 0
addE := func(u, v int) {
b, w := u, v
if !isBlack[b] {
b, w = w, b
}
edges = append(edges, Edge{id: edgeCount, B: b, W: w})
adjList[u] = append(adjList[u], AdjEdge{to: v, edgeIdx: edgeCount})
adjList[v] = append(adjList[v], AdjEdge{to: u, edgeIdx: edgeCount})
edgeCount++
}
for i := 0; i < n; i++ {
for j := 0; j < m; j++ {
if cellID[i][j] != -1 {
if i+1 < n && cellID[i+1][j] != -1 {
addE(cellID[i][j], cellID[i+1][j])
}
if j+1 < m && cellID[i][j+1] != -1 {
addE(cellID[i][j], cellID[i][j+1])
}
}
}
}
degE := make([]int, V)
for _, e := range edges {
degE[e.B]++
degE[e.W]++
}
cap := make([]int, V)
possible := true
for i := 0; i < V; i++ {
if isBlack[i] {
if i == r_id {
cap[i] = 1000000
} else {
cap[i] = degE[i] - 2
if cap[i] < 0 {
possible = false
}
}
}
}
if !possible {
fmt.Fprintln(writer, "NO")
continue
}
target := edgeCount - V + 1
inC := make([]bool, edgeCount)
curCount := make([]int, V)
q := make([]int, V)
if V > 0 {
visInit := make([]bool, V)
head, tail := 0, 0
q[tail] = 0
tail++
visInit[0] = true
connCount := 1
for head < tail {
u := q[head]
head++
for _, adj := range adjList[u] {
if !visInit[adj.to] {
visInit[adj.to] = true
q[tail] = adj.to
tail++
connCount++
}
}
}
if connCount < V {
possible = false
}
}
if !possible {
fmt.Fprintln(writer, "NO")
continue
}
C_size := 0
qE := make([]int, edgeCount)
for C_size < target {
X1 := make([]bool, edgeCount)
bridgeComponents := make([][]bool, edgeCount)
for x := 0; x < edgeCount; x++ {
if !inC[x] {
vis := make([]bool, V)
head, tail := 0, 0
q[tail] = edges[x].B
tail++
vis[edges[x].B] = true
count := 1
for head < tail {
u := q[head]
head++
for _, adj := range adjList[u] {
if adj.edgeIdx == x || inC[adj.edgeIdx] {
continue
}
v := adj.to
if !vis[v] {
vis[v] = true
q[tail] = v
tail++
count++
}
}
}
if count < V {
X1[x] = false
bridgeComponents[x] = vis
} else {
X1[x] = true
}
}
}
X2 := make([]bool, edgeCount)
for x := 0; x < edgeCount; x++ {
if !inC[x] {
b := edges[x].B
if curCount[b] < cap[b] {
X2[x] = true
}
}
}
target_node := -1
dist := make([]int, edgeCount)
for i := 0; i < edgeCount; i++ {
dist[i] = -1
}
parent := make([]int, edgeCount)
head, tail := 0, 0
for x := 0; x < edgeCount; x++ {
if !inC[x] && X1[x] {
if X2[x] {
target_node = x
break
}
dist[x] = 0
parent[x] = -1
qE[tail] = x
tail++
}
}
if target_node == -1 {
bfsLoop:
for head < tail {
curr := qE[head]
head++
if !inC[curr] {
for y := 0; y < edgeCount; y++ {
if inC[y] && dist[y] == -1 {
canGo := false
if X1[curr] {
canGo = true
} else {
vB, vW := edges[y].B, edges[y].W
if bridgeComponents[curr][vB] != bridgeComponents[curr][vW] {
canGo = true
}
}
if canGo {
dist[y] = dist[curr] + 1
parent[y] = curr
qE[tail] = y
tail++
}
}
}
} else {
for x := 0; x < edgeCount; x++ {
if !inC[x] && dist[x] == -1 {
if X2[x] {
dist[x] = dist[curr] + 1
parent[x] = curr
target_node = x
break bfsLoop
} else if edges[x].B == edges[curr].B {
dist[x] = dist[curr] + 1
parent[x] = curr
qE[tail] = x
tail++
}
}
}
}
}
}
if target_node == -1 {
break
}
curr := target_node
for curr != -1 {
if inC[curr] {
inC[curr] = false
curCount[edges[curr].B]--
C_size--
} else {
inC[curr] = true
curCount[edges[curr].B]++
C_size++
}
curr = parent[curr]
}
}
if C_size < target {
fmt.Fprintln(writer, "NO")
} else {
fmt.Fprintln(writer, "YES")
ans := make([][]byte, 2*n-1)
for i := range ans {
ans[i] = make([]byte, 2*m-1)
for j := range ans[i] {
ans[i][j] = ' '
}
}
for i := 0; i < n; i++ {
for j := 0; j < m; j++ {
if cellID[i][j] != -1 {
ans[2*i][2*j] = 'O'
} else {
ans[2*i][2*j] = 'X'
}
}
}
for i := 0; i < n; i++ {
for j := 0; j < m-1; j++ {
u := cellID[i][j]
v := cellID[i][j+1]
hasWall := true
if u != -1 && v != -1 {
for _, adj := range adjList[u] {
if adj.to == v && !inC[adj.edgeIdx] {
hasWall = false
break
}
}
}
if hasWall {
ans[2*i][2*j+1] = ' '
} else {
ans[2*i][2*j+1] = 'O'
}
}
}
for i := 0; i < n-1; i++ {
for j := 0; j < m; j++ {
u := cellID[i][j]
v := cellID[i+1][j]
hasWall := true
if u != -1 && v != -1 {
for _, adj := range adjList[u] {
if adj.to == v && !inC[adj.edgeIdx] {
hasWall = false
break
}
}
}
if hasWall {
ans[2*i+1][2*j] = ' '
} else {
ans[2*i+1][2*j] = 'O'
}
}
}
for i := 0; i < n-1; i++ {
for j := 0; j < m-1; j++ {
ans[2*i+1][2*j+1] = ' '
}
}
for i := 0; i < 2*n-1; i++ {
fmt.Fprintln(writer, string(ans[i]))
}
}
}
}