結果

問題 No.2689 Populous
ユーザー 👑 SPD_9X2SPD_9X2
提出日時 2023-12-14 14:36:29
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,589 bytes
コンパイル時間 460 ms
コンパイル使用メモリ 81,700 KB
実行使用メモリ 83,932 KB
最終ジャッジ日時 2024-02-24 05:37:14
合計ジャッジ時間 3,749 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

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