結果

問題 No.1916 Making Palindrome on Gird
ユーザー lam6er
提出日時 2025-04-09 21:01:04
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,476 bytes
コンパイル時間 300 ms
コンパイル使用メモリ 82,240 KB
実行使用メモリ 266,160 KB
最終ジャッジ日時 2025-04-09 21:02:19
合計ジャッジ時間 14,073 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20 WA * 5 TLE * 1 -- * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 10**9 + 7

H, W = map(int, input().split())
grid = [input().strip() for _ in range(H)]

if H == 1 and W == 1:
    print(1)
else:
    max_d = (H + W - 2) // 2
    from collections import defaultdict

    prev_dp = defaultdict(int)
    # Initialize for d=0
    if grid[0][0] == grid[H-1][W-1]:
        prev_dp[(1, 1, H, W)] = 1

    for d in range(max_d):
        next_dp = defaultdict(int)
        for (i, j, k, l), cnt in prev_dp.items():
            if grid[i-1][j-1] != grid[k-1][l-1]:
                continue
            # Generate start moves (down or right)
            start_moves = []
            if i < H:
                start_moves.append((i+1, j))
            if j < W:
                start_moves.append((i, j+1))
            # Generate end moves (up or left)
            end_moves = []
            if k > 1:
                end_moves.append((k-1, l))
            if l > 1:
                end_moves.append((k, l-1))
            # Process all combinations
            for new_i, new_j in start_moves:
                for new_k, new_l in end_moves:
                    if grid[new_i-1][new_j-1] == grid[new_k-1][new_l-1]:
                        next_dp[(new_i, new_j, new_k, new_l)] = (next_dp[(new_i, new_j, new_k, new_l)] + cnt) % MOD
        prev_dp = next_dp

    # Sum all states where (i,j) == (k,l)
    answer = 0
    for (i, j, k, l), cnt in prev_dp.items():
        if i == k and j == l:
            answer = (answer + cnt) % MOD

    print(answer)
0