結果

問題 No.2689 Populous
ユーザー 👑 SPD_9X2SPD_9X2
提出日時 2023-12-11 15:52:11
言語 PyPy3
(7.3.15)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 2,482 bytes
コンパイル時間 273 ms
コンパイル使用メモリ 81,984 KB
実行使用メモリ 85,000 KB
最終ジャッジ日時 2024-09-29 09:50:57
合計ジャッジ時間 3,808 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 39 ms
53,272 KB
testcase_01 AC 39 ms
52,972 KB
testcase_02 AC 39 ms
53,512 KB
testcase_03 AC 42 ms
53,164 KB
testcase_04 WA -
testcase_05 AC 38 ms
52,368 KB
testcase_06 WA -
testcase_07 AC 40 ms
54,052 KB
testcase_08 WA -
testcase_09 AC 40 ms
52,680 KB
testcase_10 WA -
testcase_11 AC 40 ms
52,704 KB
testcase_12 AC 40 ms
52,616 KB
testcase_13 AC 40 ms
52,564 KB
testcase_14 WA -
testcase_15 AC 39 ms
52,992 KB
testcase_16 AC 41 ms
53,672 KB
testcase_17 AC 40 ms
53,560 KB
testcase_18 WA -
testcase_19 AC 39 ms
53,412 KB
testcase_20 AC 145 ms
84,196 KB
testcase_21 AC 144 ms
84,384 KB
testcase_22 AC 144 ms
84,620 KB
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 AC 143 ms
84,288 KB
testcase_29 AC 145 ms
84,576 KB
testcase_30 AC 144 ms
84,336 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_diff = []
tate_diff = []

last = False
for i in range(H):
    diff = abs(A[i][0] - A[i][-1])
    if diff > W-1:
        yoko_diff.append(diff - (W-1))

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

yoko = []
tate = []

for i in range(len(yoko_diff)):
    if i == 0 or max(yoko_diff[i-1],yoko_diff[i]) <= 2:
        yoko.append(1)
    else:
        yoko[-1] += 1

for i in range(len(tate_diff)):
    if i == 0 or max(tate_diff[i-1],tate_diff[i]) <= 2:
        tate.append(1)
    else:
        tate[-1] += 1

assert len(yoko) * len(tate) == 0

ans = 1
if len(yoko) > 0:

    dp = [[0] * (W-2) for i in range(H)]

    for i in range(H):
        if i == 0:
            dp[i] = [1] * (W-2)
        else:
            for j in range(W-2):
                nsum = dp[i-1][j]
                if j != 0:
                    nsum += dp[i-1][j-1]
                if j != W-3:
                    nsum += dp[i-1][j+1]
                dp[i][j] = nsum % mod

    dpsum = [ sum(dp[i])%mod for i in range(H) ]

    for L in yoko:
        ans *= dpsum[L-1]
        ans %= mod

else:

    dp = [[0] * (H-2) for j in range(W)]

    for j in range(W):
        if j == 0:
            dp[j] = [1] * (H-2)
        else:
            for i in range(H-2):
                nsum = dp[j-1][i]
                if i != 0:
                    nsum += dp[j-1][i-1]
                if i != H-3:
                    nsum += dp[j-1][i+1]
                dp[j][i] = nsum % mod

    dpsum = [ sum(dp[j])%mod for j in range(W) ]

    ans = 1
    for L in tate:
        ans *= dpsum[L-1]
        ans %= mod

print (ans % mod)
    
#print (yoko,file=sys.stderr)
#print (tate,file=sys.stderr)
0