120152024-11-24 23:49:3842Bináris mátrixpython3Időlimit túllépés 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()
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva16ms3384 KiB
subtask29/9
2Elfogadva17ms3604 KiB
3Elfogadva17ms3376 KiB
4Elfogadva17ms3384 KiB
5Elfogadva17ms3400 KiB
6Elfogadva17ms3332 KiB
7Elfogadva17ms3208 KiB
8Elfogadva17ms3296 KiB
9Elfogadva17ms3204 KiB
10Elfogadva17ms3580 KiB
11Elfogadva17ms3428 KiB
12Elfogadva17ms3224 KiB
13Elfogadva17ms3384 KiB
14Elfogadva17ms3384 KiB
15Elfogadva16ms3340 KiB
16Elfogadva17ms3384 KiB
17Elfogadva17ms3336 KiB
subtask312/12
18Elfogadva17ms3624 KiB
19Elfogadva19ms3384 KiB
20Elfogadva19ms3392 KiB
21Elfogadva17ms3332 KiB
22Elfogadva17ms3416 KiB
23Elfogadva19ms3232 KiB
24Elfogadva19ms3384 KiB
25Elfogadva19ms3232 KiB
subtask420/20
26Elfogadva17ms3604 KiB
27Elfogadva17ms3376 KiB
28Elfogadva17ms3384 KiB
29Elfogadva17ms3400 KiB
30Elfogadva17ms3332 KiB
31Elfogadva17ms3208 KiB
32Elfogadva17ms3296 KiB
33Elfogadva17ms3204 KiB
34Elfogadva17ms3580 KiB
35Elfogadva17ms3428 KiB
36Elfogadva17ms3224 KiB
37Elfogadva17ms3384 KiB
38Elfogadva17ms3384 KiB
39Elfogadva16ms3340 KiB
40Elfogadva17ms3384 KiB
41Elfogadva17ms3336 KiB
42Elfogadva17ms3384 KiB
43Elfogadva17ms3368 KiB
44Elfogadva28ms3520 KiB
45Elfogadva17ms3396 KiB
46Elfogadva17ms3244 KiB
47Elfogadva23ms3468 KiB
48Elfogadva20ms3444 KiB
49Elfogadva20ms3384 KiB
50Elfogadva20ms3416 KiB
51Elfogadva16ms3276 KiB
52Elfogadva17ms3236 KiB
53Elfogadva19ms3336 KiB
subtask50/59
54Elfogadva16ms3568 KiB
55Elfogadva17ms3604 KiB
56Elfogadva17ms3376 KiB
57Elfogadva17ms3384 KiB
58Elfogadva17ms3400 KiB
59Elfogadva17ms3332 KiB
60Elfogadva17ms3208 KiB
61Elfogadva17ms3296 KiB
62Elfogadva17ms3204 KiB
63Elfogadva17ms3580 KiB
64Elfogadva17ms3428 KiB
65Elfogadva17ms3224 KiB
66Elfogadva17ms3384 KiB
67Elfogadva17ms3384 KiB
68Elfogadva16ms3340 KiB
69Elfogadva17ms3384 KiB
70Elfogadva17ms3336 KiB
71Elfogadva17ms3624 KiB
72Elfogadva19ms3384 KiB
73Elfogadva19ms3392 KiB
74Elfogadva17ms3332 KiB
75Elfogadva17ms3416 KiB
76Elfogadva19ms3232 KiB
77Elfogadva19ms3384 KiB
78Elfogadva19ms3232 KiB
79Elfogadva17ms3384 KiB
80Elfogadva17ms3368 KiB
81Elfogadva28ms3520 KiB
82Elfogadva17ms3396 KiB
83Elfogadva17ms3244 KiB
84Elfogadva23ms3468 KiB
85Elfogadva20ms3444 KiB
86Elfogadva20ms3384 KiB
87Elfogadva20ms3416 KiB
88Elfogadva16ms3276 KiB
89Elfogadva17ms3236 KiB
90Elfogadva19ms3336 KiB
91Időlimit túllépés1.085s7756 KiB
92Időlimit túllépés1.087s5680 KiB
93Elfogadva405ms3900 KiB
94Elfogadva231ms3640 KiB
95Elfogadva81ms3384 KiB
96Elfogadva52ms3532 KiB
97Elfogadva50ms3392 KiB
98Elfogadva37ms3320 KiB