120152024-11-24 23:49:3842Bináris mátrixpython3Time limit exceeded 41/1001.087s7756 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
1Accepted16ms3384 KiB
subtask29/9
2Accepted17ms3604 KiB
3Accepted17ms3376 KiB
4Accepted17ms3384 KiB
5Accepted17ms3400 KiB
6Accepted17ms3332 KiB
7Accepted17ms3208 KiB
8Accepted17ms3296 KiB
9Accepted17ms3204 KiB
10Accepted17ms3580 KiB
11Accepted17ms3428 KiB
12Accepted17ms3224 KiB
13Accepted17ms3384 KiB
14Accepted17ms3384 KiB
15Accepted16ms3340 KiB
16Accepted17ms3384 KiB
17Accepted17ms3336 KiB
subtask312/12
18Accepted17ms3624 KiB
19Accepted19ms3384 KiB
20Accepted19ms3392 KiB
21Accepted17ms3332 KiB
22Accepted17ms3416 KiB
23Accepted19ms3232 KiB
24Accepted19ms3384 KiB
25Accepted19ms3232 KiB
subtask420/20
26Accepted17ms3604 KiB
27Accepted17ms3376 KiB
28Accepted17ms3384 KiB
29Accepted17ms3400 KiB
30Accepted17ms3332 KiB
31Accepted17ms3208 KiB
32Accepted17ms3296 KiB
33Accepted17ms3204 KiB
34Accepted17ms3580 KiB
35Accepted17ms3428 KiB
36Accepted17ms3224 KiB
37Accepted17ms3384 KiB
38Accepted17ms3384 KiB
39Accepted16ms3340 KiB
40Accepted17ms3384 KiB
41Accepted17ms3336 KiB
42Accepted17ms3384 KiB
43Accepted17ms3368 KiB
44Accepted28ms3520 KiB
45Accepted17ms3396 KiB
46Accepted17ms3244 KiB
47Accepted23ms3468 KiB
48Accepted20ms3444 KiB
49Accepted20ms3384 KiB
50Accepted20ms3416 KiB
51Accepted16ms3276 KiB
52Accepted17ms3236 KiB
53Accepted19ms3336 KiB
subtask50/59
54Accepted16ms3568 KiB
55Accepted17ms3604 KiB
56Accepted17ms3376 KiB
57Accepted17ms3384 KiB
58Accepted17ms3400 KiB
59Accepted17ms3332 KiB
60Accepted17ms3208 KiB
61Accepted17ms3296 KiB
62Accepted17ms3204 KiB
63Accepted17ms3580 KiB
64Accepted17ms3428 KiB
65Accepted17ms3224 KiB
66Accepted17ms3384 KiB
67Accepted17ms3384 KiB
68Accepted16ms3340 KiB
69Accepted17ms3384 KiB
70Accepted17ms3336 KiB
71Accepted17ms3624 KiB
72Accepted19ms3384 KiB
73Accepted19ms3392 KiB
74Accepted17ms3332 KiB
75Accepted17ms3416 KiB
76Accepted19ms3232 KiB
77Accepted19ms3384 KiB
78Accepted19ms3232 KiB
79Accepted17ms3384 KiB
80Accepted17ms3368 KiB
81Accepted28ms3520 KiB
82Accepted17ms3396 KiB
83Accepted17ms3244 KiB
84Accepted23ms3468 KiB
85Accepted20ms3444 KiB
86Accepted20ms3384 KiB
87Accepted20ms3416 KiB
88Accepted16ms3276 KiB
89Accepted17ms3236 KiB
90Accepted19ms3336 KiB
91Time limit exceeded1.085s7756 KiB
92Time limit exceeded1.087s5680 KiB
93Accepted405ms3900 KiB
94Accepted231ms3640 KiB
95Accepted81ms3384 KiB
96Accepted52ms3532 KiB
97Accepted50ms3392 KiB
98Accepted37ms3320 KiB