結果
問題 | No.1916 Making Palindrome on Gird |
ユーザー |
![]() |
提出日時 | 2022-04-29 23:31:56 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,592 ms / 3,000 ms |
コード長 | 1,762 bytes |
コンパイル時間 | 233 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 181,652 KB |
最終ジャッジ日時 | 2024-06-29 05:17:50 |
合計ジャッジ時間 | 14,862 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
from collections import Counterfrom collections import defaultdictmod = 10 ** 9 + 7U = 201H, W = map(int, input().split())G = [input() for _ in range(H)]if H == 1 and W == 1:print(1)exit()def id(x, y, xx, yy):res = xres = res * U + yres = res * U + xxres = res * U + yyreturn resdef parse(m):m, yy = divmod(m, U)m, xx = divmod(m, U)x, y = divmod(m, U)return x, y, xx, yyif G[0][0] != G[H-1][W-1]:print(0)exit()dp = defaultdict(int)dp[id(0, 0, H-1, W-1)] = 1while True:update = Falsefinish = Falsendp = defaultdict(int)for k, v in dp.items():x, y, xx, yy = parse(k)for di, dj in [(0, 1), (1, 0)]:nx = x + diny = y + djif nx < 0 or nx >= H or ny < 0 or ny >= W:continuefor ddi, ddj in [(0, -1), (-1, 0)]:nnx = xx + ddinny = yy + ddjif nnx < 0 or nnx >= H or nny < 0 or nny >= W:continueif G[nx][ny] != G[nnx][nny]:continueif (nx + ny) >= (nnx + nny):finish = Trueif (H + W - 1) % 2 == 1 and (nx, ny) != (nnx, nny):continueif (H + W - 1) % 2 == 0 and ((x, y) != (nnx, nny) or (nx, ny) != (xx, yy)):continuendp[id(nx, ny, nnx, nny)] += vndp[id(nx, ny, nnx, nny)] %= modupdate = Truedp = ndpif finish:breakif not update:breakif not finish:print(0)else:ans = 0for k, v in dp.items():ans += vans %= modprint(ans)