結果
問題 | No.2064 Smallest Sequence on Grid |
ユーザー |
![]() |
提出日時 | 2021-09-29 00:37:19 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,496 ms / 3,000 ms |
コード長 | 869 bytes |
コンパイル時間 | 454 ms |
コンパイル使用メモリ | 82,040 KB |
実行使用メモリ | 181,816 KB |
最終ジャッジ日時 | 2024-11-16 01:33:09 |
合計ジャッジ時間 | 24,359 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 29 |
ソースコード
h,w = map(int, input().split()) Alpha = "ABCDEFGHIJKLMNOPQRSTUVWXYZ" alpha = "abcdefghijklmnopqrstuvwxyz" Dict_alpha = {} dict_alpha = {} for i in range(26): Dict_alpha[Alpha[i]] = i dict_alpha[alpha[i]] = i Dec = lambda x:Dict_alpha[x] dec = lambda x:dict_alpha[x] s = [list(map(dec, list(input()))) + [26] for i in range(h)] + [[26] * w] #print(s) st = {(0,0)} ans = [alpha[s[0][0]]] for i in range(h+w-2): mn = 100 nst = set() for jx, jy in st: t = s[jx+1][jy] if t == mn: nst.add((jx+1, jy)) elif t < mn: mn = t nst = {(jx+1, jy)} t = s[jx][jy+1] if t == mn: nst.add((jx, jy+1)) elif t < mn: mn = t nst = {(jx, jy+1)} st = nst #print(len(st)) #print(mn) ans.append(alpha[mn]) print("".join(ans))