結果

問題 No.2689 Populous
コンテスト
ユーザー 👑 SPD_9X2
提出日時 2024-02-24 05:07:23
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 124 ms / 2,000 ms
コード長 2,250 bytes
コンパイル時間 494 ms
コンパイル使用メモリ 83,072 KB
実行使用メモリ 85,328 KB
最終ジャッジ日時 2024-09-29 09:51:03
合計ジャッジ時間 3,338 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

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