結果

問題 No.1916 Making Palindrome on Gird
コンテスト
ユーザー LyricalMaestro
提出日時 2025-03-16 04:20:16
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,598 bytes
コンパイル時間 307 ms
コンパイル使用メモリ 82,356 KB
実行使用メモリ 282,020 KB
最終ジャッジ日時 2025-03-16 04:20:37
合計ジャッジ時間 20,488 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 25 TLE * 1 -- * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

## https://yukicoder.me/problems/no/1916

from collections import deque

MOD = 10 ** 9 + 7

DIRECTION0 = ((1, 0), (0, 1))
DIRECTION1 = ((-1, 0), (0, - 1))

def main():
    H, W = map(int, input().split())
    S = []
    for _ in range(H):
        S.append(input())

    if S[0][0] != S[H - 1][W - 1]:
        print(0)
        return
    
    dp = {(0, 0, H - 1, W - 1): 1}
    queue = deque()
    queue.append((0, 0, H - 1, W - 1))
    answer = 0
    while len(queue) > 0:
        h0, w0, h1, w1 = queue.popleft()
        x = dp[(h0, w0, h1, w1)]
        if abs(h0 - h1) + abs(w0 - w1) <= 1:
            answer += x
            answer %= MOD
            continue

        for dh0, dw0 in DIRECTION0:
            new_h0 = dh0 + h0
            new_w0 = dw0 + w0
            if not (0 <= new_h0 < H and 0 <= new_w0 < W):
                continue

            for dh1, dw1 in DIRECTION1:
                new_h1 = dh1 + h1
                new_w1 = dw1 + w1
                if not (0 <= new_h1 < H and 0 <= new_w1 < W):
                    continue

                if not (new_h0 <= new_h1 and new_w0 <= new_w1):
                    continue

                if S[new_h0][new_w0] == S[new_h1][new_w1]:
                    y = (new_h0, new_w0, new_h1, new_w1)
                    queued = True
                    if y not in dp:
                        dp[y] = 0
                        queued = False

                    dp[y] += x
                    dp[y] %= MOD
                    if not queued:
                        queue.append(y)
    print(answer)






if __name__ == "__main__":
    main()
0