結果
問題 |
No.2064 Smallest Sequence on Grid
|
ユーザー |
|
提出日時 | 2024-11-11 20:15:29 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,116 bytes |
コンパイル時間 | 563 ms |
コンパイル使用メモリ | 82,008 KB |
実行使用メモリ | 504,704 KB |
最終ジャッジ日時 | 2024-11-11 20:16:09 |
合計ジャッジ時間 | 25,462 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 11 WA * 17 TLE * 1 |
ソースコード
H,W = map(int,input().split()) S = [list(input()) for _ in range(H)] INFTY = 10**9 D = {chr(i):i-96 for i in range(97,123)} D[INFTY] = INFTY Pa = {} dp = [[INFTY for _ in range(W)] for _ in range(H)] dp[0][0] = D[S[0][0]] Pa[(0,0)] = -1 for i in range(H): for j in range(W): if i+1<H and j+1<W and D[S[i][j+1]]<=D[S[i+1][j]]: if dp[i][j]+D[S[i][j+1]]<dp[i][j+1]: dp[i][j+1] = dp[i][j]+D[S[i][j+1]] Pa[(i,j+1)] = (i,j) elif i+1<H and j+1<W and D[S[i][j+1]]>=D[S[i+1][j]]: if dp[i][j]+D[S[i+1][j]]<dp[i+1][j]: dp[i+1][j] = dp[i][j]+D[S[i+1][j]] Pa[(i+1,j)] = (i,j) elif i==H-1 and j+1<W: if dp[i][j]+D[S[i][j+1]]<dp[i][j+1]: dp[i][j+1] = dp[i][j]+D[S[i][j+1]] Pa[(i,j+1)] = (i,j) elif i+1<H and j==W-1: if dp[i][j]+D[S[i+1][j]]<dp[i+1][j]: dp[i+1][j] = dp[i][j]+D[S[i+1][j]] Pa[(i+1,j)] = (i,j) T = [] cur = (H-1,W-1) while cur!=-1: T.append(S[cur[0]][cur[1]]) cur = Pa[cur] print("".join(T[::-1]))