12015 | 2024-11-24 23:49:38 | 42 | Bináris mátrix | python3 | Time limit exceeded 41/100 | 1.087s | 7756 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()
Subtask | Sum | Test | Verdict | Time | Memory | ||
---|---|---|---|---|---|---|---|
subtask1 | 0/0 | ||||||
1 | Accepted | 16ms | 3384 KiB | ||||
subtask2 | 9/9 | ||||||
2 | Accepted | 17ms | 3604 KiB | ||||
3 | Accepted | 17ms | 3376 KiB | ||||
4 | Accepted | 17ms | 3384 KiB | ||||
5 | Accepted | 17ms | 3400 KiB | ||||
6 | Accepted | 17ms | 3332 KiB | ||||
7 | Accepted | 17ms | 3208 KiB | ||||
8 | Accepted | 17ms | 3296 KiB | ||||
9 | Accepted | 17ms | 3204 KiB | ||||
10 | Accepted | 17ms | 3580 KiB | ||||
11 | Accepted | 17ms | 3428 KiB | ||||
12 | Accepted | 17ms | 3224 KiB | ||||
13 | Accepted | 17ms | 3384 KiB | ||||
14 | Accepted | 17ms | 3384 KiB | ||||
15 | Accepted | 16ms | 3340 KiB | ||||
16 | Accepted | 17ms | 3384 KiB | ||||
17 | Accepted | 17ms | 3336 KiB | ||||
subtask3 | 12/12 | ||||||
18 | Accepted | 17ms | 3624 KiB | ||||
19 | Accepted | 19ms | 3384 KiB | ||||
20 | Accepted | 19ms | 3392 KiB | ||||
21 | Accepted | 17ms | 3332 KiB | ||||
22 | Accepted | 17ms | 3416 KiB | ||||
23 | Accepted | 19ms | 3232 KiB | ||||
24 | Accepted | 19ms | 3384 KiB | ||||
25 | Accepted | 19ms | 3232 KiB | ||||
subtask4 | 20/20 | ||||||
26 | Accepted | 17ms | 3604 KiB | ||||
27 | Accepted | 17ms | 3376 KiB | ||||
28 | Accepted | 17ms | 3384 KiB | ||||
29 | Accepted | 17ms | 3400 KiB | ||||
30 | Accepted | 17ms | 3332 KiB | ||||
31 | Accepted | 17ms | 3208 KiB | ||||
32 | Accepted | 17ms | 3296 KiB | ||||
33 | Accepted | 17ms | 3204 KiB | ||||
34 | Accepted | 17ms | 3580 KiB | ||||
35 | Accepted | 17ms | 3428 KiB | ||||
36 | Accepted | 17ms | 3224 KiB | ||||
37 | Accepted | 17ms | 3384 KiB | ||||
38 | Accepted | 17ms | 3384 KiB | ||||
39 | Accepted | 16ms | 3340 KiB | ||||
40 | Accepted | 17ms | 3384 KiB | ||||
41 | Accepted | 17ms | 3336 KiB | ||||
42 | Accepted | 17ms | 3384 KiB | ||||
43 | Accepted | 17ms | 3368 KiB | ||||
44 | Accepted | 28ms | 3520 KiB | ||||
45 | Accepted | 17ms | 3396 KiB | ||||
46 | Accepted | 17ms | 3244 KiB | ||||
47 | Accepted | 23ms | 3468 KiB | ||||
48 | Accepted | 20ms | 3444 KiB | ||||
49 | Accepted | 20ms | 3384 KiB | ||||
50 | Accepted | 20ms | 3416 KiB | ||||
51 | Accepted | 16ms | 3276 KiB | ||||
52 | Accepted | 17ms | 3236 KiB | ||||
53 | Accepted | 19ms | 3336 KiB | ||||
subtask5 | 0/59 | ||||||
54 | Accepted | 16ms | 3568 KiB | ||||
55 | Accepted | 17ms | 3604 KiB | ||||
56 | Accepted | 17ms | 3376 KiB | ||||
57 | Accepted | 17ms | 3384 KiB | ||||
58 | Accepted | 17ms | 3400 KiB | ||||
59 | Accepted | 17ms | 3332 KiB | ||||
60 | Accepted | 17ms | 3208 KiB | ||||
61 | Accepted | 17ms | 3296 KiB | ||||
62 | Accepted | 17ms | 3204 KiB | ||||
63 | Accepted | 17ms | 3580 KiB | ||||
64 | Accepted | 17ms | 3428 KiB | ||||
65 | Accepted | 17ms | 3224 KiB | ||||
66 | Accepted | 17ms | 3384 KiB | ||||
67 | Accepted | 17ms | 3384 KiB | ||||
68 | Accepted | 16ms | 3340 KiB | ||||
69 | Accepted | 17ms | 3384 KiB | ||||
70 | Accepted | 17ms | 3336 KiB | ||||
71 | Accepted | 17ms | 3624 KiB | ||||
72 | Accepted | 19ms | 3384 KiB | ||||
73 | Accepted | 19ms | 3392 KiB | ||||
74 | Accepted | 17ms | 3332 KiB | ||||
75 | Accepted | 17ms | 3416 KiB | ||||
76 | Accepted | 19ms | 3232 KiB | ||||
77 | Accepted | 19ms | 3384 KiB | ||||
78 | Accepted | 19ms | 3232 KiB | ||||
79 | Accepted | 17ms | 3384 KiB | ||||
80 | Accepted | 17ms | 3368 KiB | ||||
81 | Accepted | 28ms | 3520 KiB | ||||
82 | Accepted | 17ms | 3396 KiB | ||||
83 | Accepted | 17ms | 3244 KiB | ||||
84 | Accepted | 23ms | 3468 KiB | ||||
85 | Accepted | 20ms | 3444 KiB | ||||
86 | Accepted | 20ms | 3384 KiB | ||||
87 | Accepted | 20ms | 3416 KiB | ||||
88 | Accepted | 16ms | 3276 KiB | ||||
89 | Accepted | 17ms | 3236 KiB | ||||
90 | Accepted | 19ms | 3336 KiB | ||||
91 | Time limit exceeded | 1.085s | 7756 KiB | ||||
92 | Time limit exceeded | 1.087s | 5680 KiB | ||||
93 | Accepted | 405ms | 3900 KiB | ||||
94 | Accepted | 231ms | 3640 KiB | ||||
95 | Accepted | 81ms | 3384 KiB | ||||
96 | Accepted | 52ms | 3532 KiB | ||||
97 | Accepted | 50ms | 3392 KiB | ||||
98 | Accepted | 37ms | 3320 KiB |