120162024-11-24 23:50:1942Bináris mátrixpypy3Elfogadva 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()
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva43ms21232 KiB
subtask29/9
2Elfogadva45ms21300 KiB
3Elfogadva50ms21204 KiB
4Elfogadva48ms21204 KiB
5Elfogadva45ms21216 KiB
6Elfogadva50ms21228 KiB
7Elfogadva50ms21288 KiB
8Elfogadva43ms21216 KiB
9Elfogadva43ms21268 KiB
10Elfogadva48ms21164 KiB
11Elfogadva50ms21176 KiB
12Elfogadva45ms21180 KiB
13Elfogadva45ms21344 KiB
14Elfogadva43ms21228 KiB
15Elfogadva50ms21228 KiB
16Elfogadva43ms21304 KiB
17Elfogadva41ms21172 KiB
subtask312/12
18Elfogadva48ms21252 KiB
19Elfogadva64ms21800 KiB
20Elfogadva64ms22236 KiB
21Elfogadva43ms21356 KiB
22Elfogadva52ms21152 KiB
23Elfogadva74ms22248 KiB
24Elfogadva64ms21976 KiB
25Elfogadva63ms21960 KiB
subtask420/20
26Elfogadva45ms21300 KiB
27Elfogadva50ms21204 KiB
28Elfogadva48ms21204 KiB
29Elfogadva45ms21216 KiB
30Elfogadva50ms21228 KiB
31Elfogadva50ms21288 KiB
32Elfogadva43ms21216 KiB
33Elfogadva43ms21268 KiB
34Elfogadva48ms21164 KiB
35Elfogadva50ms21176 KiB
36Elfogadva45ms21180 KiB
37Elfogadva45ms21344 KiB
38Elfogadva43ms21228 KiB
39Elfogadva50ms21228 KiB
40Elfogadva43ms21304 KiB
41Elfogadva41ms21172 KiB
42Elfogadva43ms21164 KiB
43Elfogadva61ms21596 KiB
44Elfogadva78ms22316 KiB
45Elfogadva43ms21172 KiB
46Elfogadva45ms21320 KiB
47Elfogadva68ms22252 KiB
48Elfogadva71ms22116 KiB
49Elfogadva82ms22508 KiB
50Elfogadva72ms22504 KiB
51Elfogadva43ms21324 KiB
52Elfogadva52ms21156 KiB
53Elfogadva72ms21740 KiB
subtask559/59
54Elfogadva52ms21140 KiB
55Elfogadva45ms21300 KiB
56Elfogadva50ms21204 KiB
57Elfogadva48ms21204 KiB
58Elfogadva45ms21216 KiB
59Elfogadva50ms21228 KiB
60Elfogadva50ms21288 KiB
61Elfogadva43ms21216 KiB
62Elfogadva43ms21268 KiB
63Elfogadva48ms21164 KiB
64Elfogadva50ms21176 KiB
65Elfogadva45ms21180 KiB
66Elfogadva45ms21344 KiB
67Elfogadva43ms21228 KiB
68Elfogadva50ms21228 KiB
69Elfogadva43ms21304 KiB
70Elfogadva41ms21172 KiB
71Elfogadva48ms21252 KiB
72Elfogadva64ms21800 KiB
73Elfogadva64ms22236 KiB
74Elfogadva43ms21356 KiB
75Elfogadva52ms21152 KiB
76Elfogadva74ms22248 KiB
77Elfogadva64ms21976 KiB
78Elfogadva63ms21960 KiB
79Elfogadva43ms21164 KiB
80Elfogadva61ms21596 KiB
81Elfogadva78ms22316 KiB
82Elfogadva43ms21172 KiB
83Elfogadva45ms21320 KiB
84Elfogadva68ms22252 KiB
85Elfogadva71ms22116 KiB
86Elfogadva82ms22508 KiB
87Elfogadva72ms22504 KiB
88Elfogadva43ms21324 KiB
89Elfogadva52ms21156 KiB
90Elfogadva72ms21740 KiB
91Elfogadva597ms26148 KiB
92Elfogadva398ms25012 KiB
93Elfogadva170ms22992 KiB
94Elfogadva136ms23192 KiB
95Elfogadva89ms22764 KiB
96Elfogadva93ms22508 KiB
97Elfogadva82ms22252 KiB
98Elfogadva90ms22276 KiB