12016 | 2024-11-24 23:50:19 | 42 | Bináris mátrix | pypy3 | Elfogadva 100/100 | 597ms | 26148 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 | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
subtask1 | 0/0 | ||||||
1 | Elfogadva | 43ms | 21232 KiB | ||||
subtask2 | 9/9 | ||||||
2 | Elfogadva | 45ms | 21300 KiB | ||||
3 | Elfogadva | 50ms | 21204 KiB | ||||
4 | Elfogadva | 48ms | 21204 KiB | ||||
5 | Elfogadva | 45ms | 21216 KiB | ||||
6 | Elfogadva | 50ms | 21228 KiB | ||||
7 | Elfogadva | 50ms | 21288 KiB | ||||
8 | Elfogadva | 43ms | 21216 KiB | ||||
9 | Elfogadva | 43ms | 21268 KiB | ||||
10 | Elfogadva | 48ms | 21164 KiB | ||||
11 | Elfogadva | 50ms | 21176 KiB | ||||
12 | Elfogadva | 45ms | 21180 KiB | ||||
13 | Elfogadva | 45ms | 21344 KiB | ||||
14 | Elfogadva | 43ms | 21228 KiB | ||||
15 | Elfogadva | 50ms | 21228 KiB | ||||
16 | Elfogadva | 43ms | 21304 KiB | ||||
17 | Elfogadva | 41ms | 21172 KiB | ||||
subtask3 | 12/12 | ||||||
18 | Elfogadva | 48ms | 21252 KiB | ||||
19 | Elfogadva | 64ms | 21800 KiB | ||||
20 | Elfogadva | 64ms | 22236 KiB | ||||
21 | Elfogadva | 43ms | 21356 KiB | ||||
22 | Elfogadva | 52ms | 21152 KiB | ||||
23 | Elfogadva | 74ms | 22248 KiB | ||||
24 | Elfogadva | 64ms | 21976 KiB | ||||
25 | Elfogadva | 63ms | 21960 KiB | ||||
subtask4 | 20/20 | ||||||
26 | Elfogadva | 45ms | 21300 KiB | ||||
27 | Elfogadva | 50ms | 21204 KiB | ||||
28 | Elfogadva | 48ms | 21204 KiB | ||||
29 | Elfogadva | 45ms | 21216 KiB | ||||
30 | Elfogadva | 50ms | 21228 KiB | ||||
31 | Elfogadva | 50ms | 21288 KiB | ||||
32 | Elfogadva | 43ms | 21216 KiB | ||||
33 | Elfogadva | 43ms | 21268 KiB | ||||
34 | Elfogadva | 48ms | 21164 KiB | ||||
35 | Elfogadva | 50ms | 21176 KiB | ||||
36 | Elfogadva | 45ms | 21180 KiB | ||||
37 | Elfogadva | 45ms | 21344 KiB | ||||
38 | Elfogadva | 43ms | 21228 KiB | ||||
39 | Elfogadva | 50ms | 21228 KiB | ||||
40 | Elfogadva | 43ms | 21304 KiB | ||||
41 | Elfogadva | 41ms | 21172 KiB | ||||
42 | Elfogadva | 43ms | 21164 KiB | ||||
43 | Elfogadva | 61ms | 21596 KiB | ||||
44 | Elfogadva | 78ms | 22316 KiB | ||||
45 | Elfogadva | 43ms | 21172 KiB | ||||
46 | Elfogadva | 45ms | 21320 KiB | ||||
47 | Elfogadva | 68ms | 22252 KiB | ||||
48 | Elfogadva | 71ms | 22116 KiB | ||||
49 | Elfogadva | 82ms | 22508 KiB | ||||
50 | Elfogadva | 72ms | 22504 KiB | ||||
51 | Elfogadva | 43ms | 21324 KiB | ||||
52 | Elfogadva | 52ms | 21156 KiB | ||||
53 | Elfogadva | 72ms | 21740 KiB | ||||
subtask5 | 59/59 | ||||||
54 | Elfogadva | 52ms | 21140 KiB | ||||
55 | Elfogadva | 45ms | 21300 KiB | ||||
56 | Elfogadva | 50ms | 21204 KiB | ||||
57 | Elfogadva | 48ms | 21204 KiB | ||||
58 | Elfogadva | 45ms | 21216 KiB | ||||
59 | Elfogadva | 50ms | 21228 KiB | ||||
60 | Elfogadva | 50ms | 21288 KiB | ||||
61 | Elfogadva | 43ms | 21216 KiB | ||||
62 | Elfogadva | 43ms | 21268 KiB | ||||
63 | Elfogadva | 48ms | 21164 KiB | ||||
64 | Elfogadva | 50ms | 21176 KiB | ||||
65 | Elfogadva | 45ms | 21180 KiB | ||||
66 | Elfogadva | 45ms | 21344 KiB | ||||
67 | Elfogadva | 43ms | 21228 KiB | ||||
68 | Elfogadva | 50ms | 21228 KiB | ||||
69 | Elfogadva | 43ms | 21304 KiB | ||||
70 | Elfogadva | 41ms | 21172 KiB | ||||
71 | Elfogadva | 48ms | 21252 KiB | ||||
72 | Elfogadva | 64ms | 21800 KiB | ||||
73 | Elfogadva | 64ms | 22236 KiB | ||||
74 | Elfogadva | 43ms | 21356 KiB | ||||
75 | Elfogadva | 52ms | 21152 KiB | ||||
76 | Elfogadva | 74ms | 22248 KiB | ||||
77 | Elfogadva | 64ms | 21976 KiB | ||||
78 | Elfogadva | 63ms | 21960 KiB | ||||
79 | Elfogadva | 43ms | 21164 KiB | ||||
80 | Elfogadva | 61ms | 21596 KiB | ||||
81 | Elfogadva | 78ms | 22316 KiB | ||||
82 | Elfogadva | 43ms | 21172 KiB | ||||
83 | Elfogadva | 45ms | 21320 KiB | ||||
84 | Elfogadva | 68ms | 22252 KiB | ||||
85 | Elfogadva | 71ms | 22116 KiB | ||||
86 | Elfogadva | 82ms | 22508 KiB | ||||
87 | Elfogadva | 72ms | 22504 KiB | ||||
88 | Elfogadva | 43ms | 21324 KiB | ||||
89 | Elfogadva | 52ms | 21156 KiB | ||||
90 | Elfogadva | 72ms | 21740 KiB | ||||
91 | Elfogadva | 597ms | 26148 KiB | ||||
92 | Elfogadva | 398ms | 25012 KiB | ||||
93 | Elfogadva | 170ms | 22992 KiB | ||||
94 | Elfogadva | 136ms | 23192 KiB | ||||
95 | Elfogadva | 89ms | 22764 KiB | ||||
96 | Elfogadva | 93ms | 22508 KiB | ||||
97 | Elfogadva | 82ms | 22252 KiB | ||||
98 | Elfogadva | 90ms | 22276 KiB |