結果
問題 | No.1916 Making Palindrome on Gird |
ユーザー | lilictaka |
提出日時 | 2022-04-29 23:27:15 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,871 bytes |
コンパイル時間 | 299 ms |
コンパイル使用メモリ | 86,768 KB |
実行使用メモリ | 86,960 KB |
最終ジャッジ日時 | 2023-09-11 15:03:10 |
合計ジャッジ時間 | 7,269 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 88 ms
71,644 KB |
testcase_01 | AC | 85 ms
71,172 KB |
testcase_02 | AC | 121 ms
76,704 KB |
testcase_03 | WA | - |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | AC | 90 ms
72,356 KB |
testcase_10 | AC | 87 ms
71,508 KB |
testcase_11 | WA | - |
testcase_12 | WA | - |
testcase_13 | WA | - |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | WA | - |
testcase_17 | WA | - |
testcase_18 | WA | - |
testcase_19 | WA | - |
testcase_20 | WA | - |
testcase_21 | WA | - |
testcase_22 | WA | - |
testcase_23 | AC | 132 ms
80,040 KB |
testcase_24 | AC | 120 ms
77,652 KB |
testcase_25 | AC | 130 ms
80,720 KB |
testcase_26 | AC | 135 ms
80,232 KB |
testcase_27 | AC | 118 ms
77,560 KB |
testcase_28 | AC | 183 ms
86,960 KB |
testcase_29 | WA | - |
testcase_30 | AC | 187 ms
86,472 KB |
testcase_31 | AC | 193 ms
86,888 KB |
testcase_32 | AC | 184 ms
86,824 KB |
ソースコード
from collections import deque H,W = map(int,input().split()) S = [] edge = [[[] for _ in range(W)] for _ in range(H)] IN = [[0] * W for _ in range(H)] flag = [[False] * W for _ in range(H)] def check(h,w): if 0 <= h < H and 0 <= w < W: return True else: return False def e(h,w,t): for dh,dw in [(-1,0),(1,0),(0,1),(0,-1)]: nh = h + dh nw = w + dw if check(nh,nw) : if flag[nh][nw]: if t == 0: edge[h][w].append((nh,nw)) IN[nh][nw] += 1 else: edge[nh][nw].append((h,w)) IN[h][w] += 1 for _ in range(H): s = list(map(lambda x:ord(x) - ord('a') ,list(input()))) S.append(s) def solve(): for i in range((H+W-2)//2 + 1): k = (H + W -2)//2 - i left = set() right = set() for h in range(max(0,k-(W-1)),min(H-1,k) + 1): w = k - h left.add(S[h][w]) rk = (H+W-2 + 1)//2 + i for h in range(max(0,rk-(W-1)),min(H-1,rk) + 1): w = rk - h right.add(S[h][w]) for h in range(max(0,k-(W-1)),min(H-1,k) + 1): w = k - h if S[h][w] in right: flag[h][w] = True e(h,w,0) for h in range(max(0,rk-(W-1)),min(H-1,rk) + 1): w = rk - h if S[h][w] in left: flag[h][w] = True e(h,w,1) solve() dp = [[0] * W for _ in range(H)] cnt = [[0] * W for _ in range(H)] dp[0][0] = 1 mod = 10 ** 9 + 7 q = deque() seen = [[False] * W for _ in range(H)] q.append((0,0)) while q: h,w = q.popleft() for nh,nw in edge[h][w]: dp[nh][nw] += dp[h][w] dp[nh][nw] %= mod if not seen[nh][nw]: q.append((nh,nw)) seen[nh][nw] = True print(dp[H-1][W-1])