結果

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

ソースコード

diff #
raw source code 

mod = 10**9+7
def f(y0, x0, y1, x1):
    return y0*n*n*n + x0*n*n + y1*n + x1
def g(a):
    return a//n//n//n, a//n//n%n, a//n%n, a%n
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[f(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 d in D:
        a = D[d]
        y0, x0, y1, x1 = g(d)
        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_[f(ny0, nx0, ny1, nx1)] += a
                    D_[f(ny0, nx0, ny1, nx1)] %= mod
    D = D_
ans = 0
for d in D:
    ans = (ans + D[d]) % mod
print(ans)
0