結果

問題 No.3429 Palindromic Path (Hard)
コンテスト
ユーザー detteiuu
提出日時 2026-01-29 18:20:22
言語 PyPy3
(7.3.17)
結果
AC  
実行時間 596 ms / 2,000 ms
コード長 913 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 340 ms
コンパイル使用メモリ 82,712 KB
実行使用メモリ 108,576 KB
最終ジャッジ日時 2026-01-29 18:20:25
合計ジャッジ時間 2,351 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 7
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

MOD = 998244353

N = int(input())
C = [input() for _ in range(N)]

if C[0][0] != C[-1][-1]:
    exit(print(0))

dp = [[0]*N for _ in range(N)]
dp[0][N-1] = 1
for i in range(N-1):
    ndp = [[0]*N for _ in range(N)]
    for j in range(N):
        for k in range(N):
            if dp[j][k] == 0:
                continue
            h1, w1 = j, i-j
            h2, w2 = k, (N-1)-(i-(N-1-k))
            for a, b in [(1, 0), (0, 1)]:
                for c, d in [(1, 0), (0, 1)]:
                    if C[h1+a][w1+b] == C[h2-c][w2-d]:
                        if i < N-2:
                            ndp[j+a][k-c] += dp[j][k]
                            ndp[j+a][k-c] %= MOD
                        elif (h1+a, w1+b) == (h2-c, w2-d):
                            ndp[j+a][k-c] += dp[j][k]
                            ndp[j+a][k-c] %= MOD
    dp = ndp

ans = 0
for d in dp:
    ans += sum(d)
    ans %= MOD

print(ans)
0