結果

問題 No.2689 Populous
コンテスト
ユーザー 👑 SPD_9X2
提出日時 2023-12-14 14:36:29
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,589 bytes
コンパイル時間 494 ms
コンパイル使用メモリ 81,772 KB
実行使用メモリ 84,588 KB
最終ジャッジ日時 2024-09-29 09:50:38
合計ジャッジ時間 3,887 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 16 WA * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

"""

想定誤解法

連続すれば問答無用で隣接判定になってしまっている

"""

import sys

mod = 998244353

H,W = map(int,input().split())

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()))


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 = []

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

last = False
for j in range(W):
    diff = abs(A[0][j] - A[-1][j])
    if diff > H-1:
        if last:
            tate[-1] += 1
        else:
            tate.append(1)
        last = True
    else:
        last = False

#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 (dpsum)
#print (yoko,file=sys.stderr)
#print (tate,file=sys.stderr)
0