結果

問題 No.2689 Populous
ユーザー 👑 SPD_9X2SPD_9X2
提出日時 2024-02-24 05:07:23
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 134 ms / 2,000 ms
コード長 2,250 bytes
コンパイル時間 174 ms
コンパイル使用メモリ 81,572 KB
実行使用メモリ 84,444 KB
最終ジャッジ日時 2024-02-24 05:37:16
合計ジャッジ時間 3,509 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 39 ms
53,332 KB
testcase_01 AC 39 ms
53,332 KB
testcase_02 AC 38 ms
53,332 KB
testcase_03 AC 39 ms
53,332 KB
testcase_04 AC 38 ms
53,332 KB
testcase_05 AC 38 ms
53,332 KB
testcase_06 AC 38 ms
53,332 KB
testcase_07 AC 38 ms
53,332 KB
testcase_08 AC 38 ms
53,332 KB
testcase_09 AC 39 ms
53,332 KB
testcase_10 AC 39 ms
53,332 KB
testcase_11 AC 38 ms
53,332 KB
testcase_12 AC 39 ms
53,332 KB
testcase_13 AC 40 ms
53,332 KB
testcase_14 AC 38 ms
53,332 KB
testcase_15 AC 39 ms
53,332 KB
testcase_16 AC 38 ms
53,332 KB
testcase_17 AC 38 ms
53,332 KB
testcase_18 AC 38 ms
53,332 KB
testcase_19 AC 38 ms
53,332 KB
testcase_20 AC 115 ms
83,804 KB
testcase_21 AC 114 ms
83,804 KB
testcase_22 AC 116 ms
83,804 KB
testcase_23 AC 131 ms
84,444 KB
testcase_24 AC 130 ms
84,444 KB
testcase_25 AC 129 ms
84,444 KB
testcase_26 AC 124 ms
84,444 KB
testcase_27 AC 134 ms
84,444 KB
testcase_28 AC 134 ms
83,932 KB
testcase_29 AC 126 ms
83,932 KB
testcase_30 AC 126 ms
83,932 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

"""

訂正版

"""

import sys

mod = 998244353

H,W = map(int,input().split())
assert 3 <= H <= 1000
assert 3 <= W <= 1000

A = [[None] * W for i in range(H)]

# input
A[0] = list(map(int,input().split()))
for i in range(1,H-1):
    A[i][0],A[i][-1] = map(int,input().split())
A[-1] = list(map(int,input().split()))

for i in range(H):
    for j in range(W):
        if A[i][j] != None:
            assert 1 <= A[i][j] <= 2000

flag = True
for i in range(H):
    for j in range(W):
        if A[i][j] == None:
            continue

        for i2,j2 in ( (i+1,j),(i,j+1) ):
            if i2 < H and j2 < W and A[i2][j2] != None:

                if abs(A[i][j] - A[i2][j2]) > 1:
                    flag = False

if not flag:
    print (-1)
    sys.exit()

yoko_knum = 0
tate_knum = 0

for i in range(H):
    diff = abs(A[i][0] - A[i][-1])
    if diff > W-1:
        yoko_knum += 1

for j in range(W):
    diff = abs(A[0][j] - A[-1][j])
    if diff > H-1:
        tate_knum += 1

assert yoko_knum * tate_knum == 0

if yoko_knum == tate_knum == 0:
    print (1)
    sys.exit()

if tate_knum > 0:
    A = [[ A[i][j] for i in range(H) ] for j in range(W)]
    H,W = W,H
    yoko_knum,tate_knum = tate_knum,yoko_knum
    

dp = [0] * W ; dp[0] = 1

for i in range(1,H-1):
    diff = abs(A[i][0] - A[i][-1])

    if diff > W-1:
        Lflag = ( abs(A[i][0]  -A[i-1][-1])>W )
        Rflag = ( abs(A[i-1][0]-A[i][-1]) > W )

        if Lflag == Rflag == False: #自由配置
            dpsum = sum(dp) % mod
            ndp = [dpsum] * W; ndp[0] = ndp[-1] = 0
            
        elif Lflag == Rflag == True: #3配置
            ndp = [0] * W
            for j in range(1,W-1):
                ndp[j] = (dp[j-1] + dp[j] + dp[j+1]) % mod

        elif Lflag: #(i,j+1)以左に置く必要がある
            ndp = [0] * W
            nsum = dp[-2] + dp[-1] 
            for j in range(W-2,0,-1):
                nsum += dp[j-1]
                nsum %= mod
                ndp[j] = nsum

        else:
            ndp = [0] * W
            nsum = dp[0] + dp[1]
            for j in range(1,W-1):
                nsum += dp[j+1]
                nsum %= mod
                ndp[j] = nsum

        dp = ndp

    #print (dp)
    
print (sum(dp) % mod)
0