結果

問題 No.3429 Palindromic Path (Hard)
コンテスト
ユーザー kidodesu
提出日時 2025-12-29 16:00:25
言語 PyPy3
(7.3.17)
結果
WA  
実行時間 -
コード長 919 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 180 ms
コンパイル使用メモリ 82,464 KB
実行使用メモリ 258,060 KB
最終ジャッジ日時 2026-01-11 13:04:20
合計ジャッジ時間 4,015 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 WA * 1
other AC * 3 TLE * 1 -- * 3
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

mod = 10**9+7
n = int(input()); assert 2 <= n <= 200
S = [input() for _ in range(n)]
from collections import defaultdict as Di
D = Di(int)
t = 0
if S[0][0] == S[-1][-1]:
    t += 1
D[(0, 0, n-1, n-1)] = t

dy = [1, 0, -1, 0]
dx = [0, 1, 0, -1]

for _ in range(n-1):
    D_ = Di(int)
    for y0, x0, y1, x1 in D:
        a = D[(y0, x0, y1, x1)]
        for d0 in range(2):
            ny0, nx0 = y0+dy[d0], x0+dx[d0]
            if not (ny0 < n and nx0 < n):
                continue
            for d1 in range(2, 4):
                ny1, nx1 = y1+dy[d1], x1+dx[d1]
                if not (0 <= ny1 and 0 <= nx1):
                    continue
                if (_ < n-2 and S[ny0][nx0] == S[ny1][nx1]) or (_ == n-2 and (ny0, nx0) == (ny1, nx1)):
                    D_[(ny0, nx0, ny1, nx1)] += a
                    D_[(ny0, nx0, ny1, nx1)] %= mod
    D = D_
ans = 0
for d in D:
    ans = (ans + D[d]) % mod
print(ans)
0