結果
問題 |
No.3199 Key-Door Grid
|
ユーザー |
|
提出日時 | 2025-07-14 14:06:46 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 764 ms / 3,000 ms |
コード長 | 1,225 bytes |
コンパイル時間 | 388 ms |
コンパイル使用メモリ | 82,848 KB |
実行使用メモリ | 121,368 KB |
最終ジャッジ日時 | 2025-07-14 14:06:59 |
合計ジャッジ時間 | 12,180 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
H, W, M = map(int, input().split()) S = [input() for _ in range(H)] si = sj = -1 gi = gj = -1 for i in range(H): for j in range(W): if S[i][j] == 'S': si, sj = i, j elif S[i][j] == 'G': gi, gj = i, j from collections import deque dp = [[[-1] * W for _ in range(H)] for _ in range(M + 1)] dp[0][si][sj] = 0 que = deque([(0, si, sj)]) di, dj = [1, 0, -1, 0], [0, 1, 0, -1] while que: m, i, j = que.popleft() for d in range(4): ni, nj = i + di[d], j + dj[d] if 0 <= ni < H and 0 <= nj < W and S[ni][nj] != '#': if S[ni][nj].isnumeric(): # 鍵 nm = int(S[ni][nj]) elif S[ni][nj].isalpha() and S[ni][nj].islower(): if ord(S[ni][nj]) == ord('a') + m - 1: # 扉 nm = m else: continue else: nm = m if dp[nm][ni][nj] == -1: dp[nm][ni][nj] = dp[m][i][j] + 1 que.append((nm, ni, nj)) ans = -1 for m in range(M + 1): if dp[m][gi][gj] != -1: if ans == -1 or ans > dp[m][gi][gj]: ans = dp[m][gi][gj] print(ans)