For problem statement at 1000-1999/1900-1999/1980-1989/1985/problemH2.txt this is a correct solution, but verifier at 1000-1999/1900-1999/1980-1989/1985/verifierH2.go ends with test 11 failed
input:
1
4 4
..#.
..##
##.#
.#.#
expected:
12
got:
13
exit status 1 can you fix the verifier? package main
import (
"bytes"
"io"
"os"
"strconv"
)
type FastScanner struct {
data []byte
idx int
n int
}
func NewFastScanner() *FastScanner {
data, _ := io.ReadAll(os.Stdin)
return &FastScanner{data: data, n: len(data)}
}
func (fs *FastScanner) skip() {
for fs.idx < fs.n && fs.data[fs.idx] <= ' ' {
fs.idx++
}
}
func (fs *FastScanner) NextInt() int {
fs.skip()
val := 0
for fs.idx < fs.n {
b := fs.data[fs.idx]
if b <= ' ' {
break
}
val = val*10 + int(b-'0')
fs.idx++
}
return val
}
func (fs *FastScanner) NextBytes() []byte {
fs.skip()
start := fs.idx
for fs.idx < fs.n && fs.data[fs.idx] > ' ' {
fs.idx++
}
return fs.data[start:fs.idx]
}
func main() {
fs := NewFastScanner()
t := fs.NextInt()
var out bytes.Buffer
for tc := 0; tc < t; tc++ {
n := fs.NextInt()
m := fs.NextInt()
nm := n * m
grid := make([]byte, nm)
rowDots := make([]int, n)
colDots := make([]int, m)
for i := 0; i < n; i++ {
s := fs.NextBytes()
base := i * m
copy(grid[base:base+m], s)
for j := 0; j < m; j++ {
if s[j] == '.' {
rowDots[i]++
colDots[j]++
}
}
}
rowDiff := make([]int, n+1)
colDiff := make([]int, m+1)
w := m + 1
diff := make([]int, (n+1)*w)
queue := make([]int, nm)
for i := 0; i < n; i++ {
base := i * m
for j := 0; j < m; j++ {
start := base + j
if grid[start] != '#' {
continue
}
grid[start] = '*'
head, tail := 0, 1
queue[0] = start
size := 0
minR, maxR := i, i
minC, maxC := j, j
for head < tail {
p := queue[head]
head++
size++
r := p / m
c := p % m
if r < minR {
minR = r
}
if r > maxR {
maxR = r
}
if c < minC {
minC = c
}
if c > maxC {
maxC = c
}
if r > 0 {
q := p - m
if grid[q] == '#' {
grid[q] = '*'
queue[tail] = q
tail++
}
}
if r+1 < n {
q := p + m
if grid[q] == '#' {
grid[q] = '*'
queue[tail] = q
tail++
}
}
if c > 0 {
q := p - 1
if grid[q] == '#' {
grid[q] = '*'
queue[tail] = q
tail++
}
}
if c+1 < m {
q := p + 1
if grid[q] == '#' {
grid[q] = '*'
queue[tail] = q
tail++
}
}
}
r1 := minR - 1
if r1 < 0 {
r1 = 0
}
r2 := maxR + 1
if r2 >= n {
r2 = n - 1
}
c1 := minC - 1
if c1 < 0 {
c1 = 0
}
c2 := maxC + 1
if c2 >= m {
c2 = m - 1
}
rowDiff[r1] += size
rowDiff[r2+1] -= size
colDiff[c1] += size
colDiff[c2+1] -= size
diff[r1*w+c1] += size
diff[(r2+1)*w+c1] -= size
diff[r1*w+c2+1] -= size
diff[(r2+1)*w+c2+1] += size
}
}
rowSum := make([]int, n)
cur := 0
for i := 0; i < n; i++ {
cur += rowDiff[i]
rowSum[i] = cur
}
colSum := make([]int, m)
cur = 0
for j := 0; j < m; j++ {
cur += colDiff[j]
colSum[j] = cur
}
ans := 0
for i := 0; i < n; i++ {
rowBase := i * w
prevRowBase := (i - 1) * w
gridBase := i * m
for j := 0; j < m; j++ {
idx := rowBase + j
v := diff[idx]
if i > 0 {
v += diff[prevRowBase+j]
}
if j > 0 {
v += diff[rowBase+j-1]
}
if i > 0 && j > 0 {
v -= diff[prevRowBase+j-1]
}
diff[idx] = v
score := rowDots[i] + colDots[j]
if grid[gridBase+j] == '.' {
score--
}
score += rowSum[i] + colSum[j] - v
if score > ans {
ans = score
}
}
}
out.WriteString(strconv.Itoa(ans))
if tc+1 < t {
out.WriteByte('\n')
}
}
os.Stdout.Write(out.Bytes())
}