Submission #59634379

Source Code Expand

h,w = map(int,input().split())
b = [input().strip() for _ in range(h)]

if h < w:
    b = list(zip(*b))
    h,w = w,h

MOD = 998244353
M = 10**(w-1)

dp = [[0,1]] # state, val
for x in range(h):
    for y in range(w):
        flags = [False, b[x][y] in "1?", b[x][y] in "2?", b[x][y] in "3?"]
        ndp = []
        for d in range(1,4):
            if not flags[d]: continue
            for state,val in dp:
                # 置ける？
                if state%10==d: continue # 上
                if y and state//M==d: continue # 左
                # 遷移
                new_state = state//10 + d*M
                if ndp and ndp[-1][0] == new_state:
                    ndp[-1][1] += val%MOD
                else:
                    ndp.append([new_state,val])
        dp = ndp

ans = sum([v for k,v in dp])
print(ans%MOD)

Submission Info

Submission Time
Task G - Count Grid 3-coloring
User convexineq
Language Python (PyPy 3.10-v7.3.12)
Score 575
Code Size 865 Byte
Status AC
Exec Time 498 ms
Memory 264344 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 575 / 575
Status
AC × 3
AC × 62
Set Name Test Cases
Sample 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt
All 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 01_test_00.txt, 01_test_01.txt, 01_test_02.txt, 01_test_03.txt, 01_test_04.txt, 01_test_05.txt, 01_test_06.txt, 01_test_07.txt, 01_test_08.txt, 01_test_09.txt, 01_test_10.txt, 01_test_11.txt, 01_test_12.txt, 01_test_13.txt, 01_test_14.txt, 01_test_15.txt, 01_test_16.txt, 01_test_17.txt, 01_test_18.txt, 01_test_19.txt, 01_test_20.txt, 01_test_21.txt, 01_test_22.txt, 01_test_23.txt, 01_test_24.txt, 01_test_25.txt, 01_test_26.txt, 01_test_27.txt, 01_test_28.txt, 01_test_29.txt, 01_test_30.txt, 01_test_31.txt, 01_test_32.txt, 01_test_33.txt, 01_test_34.txt, 01_test_35.txt, 01_test_36.txt, 01_test_37.txt, 01_test_38.txt, 01_test_39.txt, 01_test_40.txt, 01_test_41.txt, 01_test_42.txt, 01_test_43.txt, 01_test_44.txt, 01_test_45.txt, 01_test_46.txt, 01_test_47.txt, 01_test_48.txt, 01_test_49.txt, 01_test_50.txt, 01_test_51.txt, 01_test_52.txt, 01_test_53.txt, 01_test_54.txt, 01_test_55.txt, 01_test_56.txt, 01_test_57.txt, 01_test_58.txt
Case Name Status Exec Time Memory
00_sample_00.txt AC 55 ms 76304 KiB
00_sample_01.txt AC 55 ms 76448 KiB
00_sample_02.txt AC 66 ms 81268 KiB
01_test_00.txt AC 56 ms 76528 KiB
01_test_01.txt AC 55 ms 76416 KiB
01_test_02.txt AC 56 ms 76372 KiB
01_test_03.txt AC 56 ms 76196 KiB
01_test_04.txt AC 55 ms 76600 KiB
01_test_05.txt AC 55 ms 76508 KiB
01_test_06.txt AC 56 ms 76328 KiB
01_test_07.txt AC 55 ms 76712 KiB
01_test_08.txt AC 60 ms 81500 KiB
01_test_09.txt AC 64 ms 81316 KiB
01_test_10.txt AC 66 ms 81572 KiB
01_test_11.txt AC 67 ms 81840 KiB
01_test_12.txt AC 68 ms 81804 KiB
01_test_13.txt AC 68 ms 81568 KiB
01_test_14.txt AC 68 ms 81336 KiB
01_test_15.txt AC 72 ms 81588 KiB
01_test_16.txt AC 78 ms 82668 KiB
01_test_17.txt AC 85 ms 82880 KiB
01_test_18.txt AC 91 ms 83960 KiB
01_test_19.txt AC 114 ms 88452 KiB
01_test_20.txt AC 173 ms 114344 KiB
01_test_21.txt AC 218 ms 141196 KiB
01_test_22.txt AC 153 ms 103348 KiB
01_test_23.txt AC 105 ms 86956 KiB
01_test_24.txt AC 97 ms 84532 KiB
01_test_25.txt AC 85 ms 82804 KiB
01_test_26.txt AC 80 ms 83452 KiB
01_test_27.txt AC 72 ms 81364 KiB
01_test_28.txt AC 70 ms 81980 KiB
01_test_29.txt AC 66 ms 81436 KiB
01_test_30.txt AC 66 ms 81832 KiB
01_test_31.txt AC 67 ms 81476 KiB
01_test_32.txt AC 65 ms 81276 KiB
01_test_33.txt AC 63 ms 81880 KiB
01_test_34.txt AC 59 ms 81372 KiB
01_test_35.txt AC 246 ms 139732 KiB
01_test_36.txt AC 157 ms 106660 KiB
01_test_37.txt AC 66 ms 81912 KiB
01_test_38.txt AC 79 ms 82292 KiB
01_test_39.txt AC 498 ms 264344 KiB
01_test_40.txt AC 246 ms 147524 KiB
01_test_41.txt AC 64 ms 81328 KiB
01_test_42.txt AC 68 ms 81488 KiB
01_test_43.txt AC 243 ms 139460 KiB
01_test_44.txt AC 139 ms 99944 KiB
01_test_45.txt AC 65 ms 81916 KiB
01_test_46.txt AC 74 ms 82028 KiB
01_test_47.txt AC 241 ms 136336 KiB
01_test_48.txt AC 239 ms 136160 KiB
01_test_49.txt AC 236 ms 135160 KiB
01_test_50.txt AC 233 ms 134308 KiB
01_test_51.txt AC 211 ms 122900 KiB
01_test_52.txt AC 212 ms 126696 KiB
01_test_53.txt AC 78 ms 83688 KiB
01_test_54.txt AC 84 ms 89828 KiB
01_test_55.txt AC 59 ms 81456 KiB
01_test_56.txt AC 60 ms 81248 KiB
01_test_57.txt AC 56 ms 76436 KiB
01_test_58.txt AC 56 ms 76596 KiB