120162024-11-24 23:50:1942Bináris mátrixpypy3Accepted 100/100597ms26148 KiB
#!/usr/bin/env python3

from sys import stdin
input = stdin.readline

inf=10**9

def solv():
    input()
    N, M = map(int, input().split())
    S = ["" for i in range(N)]
    for i in range(N):
        S[i] = input().strip()
    if M < 3:
        row = 0
    else:
        dp11=[inf]*(M-1)
        dp00=[inf]*(M-1)
        dp10=[inf]*(M-1)
        dp01=[inf]*(M-1)
        dp11[0]=2
        dp00[0]=0
        dp10[0]=1
        dp01[0]=1
        for i in range(M-2):
            cur=set()
            for j in range(N):
                cur.add(S[j][i:i+3])
            ok000 = '000' in cur or '111' in cur
            ok100 = '100' in cur or '011' in cur
            if not ok000:
                dp00[i+1]=dp00[i]
                dp11[i+1]=1+dp11[i]
            if not ok100:
                dp00[i+1]=min(dp00[i+1],dp10[i])
                dp11[i+1]=min(dp11[i+1],1+dp01[i])
            ok010 = '010' in cur or '101' in cur
            ok001 = '001' in cur or '110' in cur
            if not ok010:
                dp10[i+1]=dp01[i]
                dp01[i+1]=1+dp10[i]
            if not ok001:
                dp10[i+1]=min(dp10[i+1],dp11[i])
                dp01[i+1]=min(dp01[i+1],1+dp00[i])
        row=min(dp00[-1],dp01[-1],dp10[-1],dp11[-1])
    if N < 3:
        col = 0
    else:
        dp11=[inf]*(N-1)
        dp00=[inf]*(N-1)
        dp10=[inf]*(N-1)
        dp01=[inf]*(N-1)
        dp11[0]=2
        dp00[0]=0
        dp10[0]=1
        dp01[0]=1
        for i in range(N-2):
            cur=set()
            for j in range(M):
                cur.add(S[i][j]+S[i+1][j]+S[i+2][j])
            ok000 = '000' in cur or '111' in cur
            ok100 = '100' in cur or '011' in cur
            if not ok000:
                dp00[i+1]=dp00[i]
                dp11[i+1]=1+dp11[i]
            if not ok100:
                dp00[i+1]=min(dp00[i+1],dp10[i])
                dp11[i+1]=min(dp11[i+1],1+dp01[i])
            ok010 = '010' in cur or '101' in cur
            ok001 = '001' in cur or '110' in cur
            if not ok010:
                dp10[i+1]=dp01[i]
                dp01[i+1]=1+dp10[i]
            if not ok001:
                dp10[i+1]=min(dp10[i+1],dp11[i])
                dp01[i+1]=min(dp01[i+1],1+dp00[i])
        col=min(dp00[-1],dp01[-1],dp10[-1],dp11[-1])
    if row+col<inf:
        print(row+col)
    else:
        print(-1)

for test in range(int(input())):
    solv()
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted43ms21232 KiB
subtask29/9
2Accepted45ms21300 KiB
3Accepted50ms21204 KiB
4Accepted48ms21204 KiB
5Accepted45ms21216 KiB
6Accepted50ms21228 KiB
7Accepted50ms21288 KiB
8Accepted43ms21216 KiB
9Accepted43ms21268 KiB
10Accepted48ms21164 KiB
11Accepted50ms21176 KiB
12Accepted45ms21180 KiB
13Accepted45ms21344 KiB
14Accepted43ms21228 KiB
15Accepted50ms21228 KiB
16Accepted43ms21304 KiB
17Accepted41ms21172 KiB
subtask312/12
18Accepted48ms21252 KiB
19Accepted64ms21800 KiB
20Accepted64ms22236 KiB
21Accepted43ms21356 KiB
22Accepted52ms21152 KiB
23Accepted74ms22248 KiB
24Accepted64ms21976 KiB
25Accepted63ms21960 KiB
subtask420/20
26Accepted45ms21300 KiB
27Accepted50ms21204 KiB
28Accepted48ms21204 KiB
29Accepted45ms21216 KiB
30Accepted50ms21228 KiB
31Accepted50ms21288 KiB
32Accepted43ms21216 KiB
33Accepted43ms21268 KiB
34Accepted48ms21164 KiB
35Accepted50ms21176 KiB
36Accepted45ms21180 KiB
37Accepted45ms21344 KiB
38Accepted43ms21228 KiB
39Accepted50ms21228 KiB
40Accepted43ms21304 KiB
41Accepted41ms21172 KiB
42Accepted43ms21164 KiB
43Accepted61ms21596 KiB
44Accepted78ms22316 KiB
45Accepted43ms21172 KiB
46Accepted45ms21320 KiB
47Accepted68ms22252 KiB
48Accepted71ms22116 KiB
49Accepted82ms22508 KiB
50Accepted72ms22504 KiB
51Accepted43ms21324 KiB
52Accepted52ms21156 KiB
53Accepted72ms21740 KiB
subtask559/59
54Accepted52ms21140 KiB
55Accepted45ms21300 KiB
56Accepted50ms21204 KiB
57Accepted48ms21204 KiB
58Accepted45ms21216 KiB
59Accepted50ms21228 KiB
60Accepted50ms21288 KiB
61Accepted43ms21216 KiB
62Accepted43ms21268 KiB
63Accepted48ms21164 KiB
64Accepted50ms21176 KiB
65Accepted45ms21180 KiB
66Accepted45ms21344 KiB
67Accepted43ms21228 KiB
68Accepted50ms21228 KiB
69Accepted43ms21304 KiB
70Accepted41ms21172 KiB
71Accepted48ms21252 KiB
72Accepted64ms21800 KiB
73Accepted64ms22236 KiB
74Accepted43ms21356 KiB
75Accepted52ms21152 KiB
76Accepted74ms22248 KiB
77Accepted64ms21976 KiB
78Accepted63ms21960 KiB
79Accepted43ms21164 KiB
80Accepted61ms21596 KiB
81Accepted78ms22316 KiB
82Accepted43ms21172 KiB
83Accepted45ms21320 KiB
84Accepted68ms22252 KiB
85Accepted71ms22116 KiB
86Accepted82ms22508 KiB
87Accepted72ms22504 KiB
88Accepted43ms21324 KiB
89Accepted52ms21156 KiB
90Accepted72ms21740 KiB
91Accepted597ms26148 KiB
92Accepted398ms25012 KiB
93Accepted170ms22992 KiB
94Accepted136ms23192 KiB
95Accepted89ms22764 KiB
96Accepted93ms22508 KiB
97Accepted82ms22252 KiB
98Accepted90ms22276 KiB