結果
問題 |
No.3199 Key-Door Grid
|
ユーザー |
![]() |
提出日時 | 2025-07-12 07:04:11 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,510 ms / 3,000 ms |
コード長 | 1,624 bytes |
コンパイル時間 | 491 ms |
コンパイル使用メモリ | 81,920 KB |
実行使用メモリ | 183,272 KB |
最終ジャッジ日時 | 2025-07-12 07:04:36 |
合計ジャッジ時間 | 23,748 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
from collections import deque def list3(a, b, c, *, val=0): return [[[val] * c for _ in range(b)] for _ in range(a)] def neighbors4(r: int, c: int) -> list[tuple[int, int]]: res = [] for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]: nr = r + dr nc = c + dc if not (0 <= nr < H and 0 <= nc < W): continue res.append((nr, nc)) return res INF = 1 << 60 H, W, M = map(int, input().split()) S = [] for _ in range(H): S.append(list(input())) def find(c): for i in range(H): for j in range(W): if S[i][j] == c: return i, j assert False sr, sc = find('S') dists = list3(H, W, 10, val=INF) dists[sr][sc][0] = 0 q = deque([(sr, sc, 0)]) while q: r, c, key = q.popleft() for nr, nc in neighbors4(r, c): if S[nr][nc] == '#': continue nk = key if S[nr][nc].islower(): a = ord(S[nr][nc]) - ord('a') + 1 if nk != a: continue if dists[nr][nc][nk] <= dists[r][c][key] + 1: continue dists[nr][nc][nk] = dists[r][c][key] + 1 q.append((nr, nc, nk)) elif S[nr][nc].isdigit(): nk = ord(S[nr][nc]) - ord('1') + 1 if dists[nr][nc][nk] <= dists[r][c][key] + 1: continue dists[nr][nc][nk] = dists[r][c][key] + 1 q.append((nr, nc, nk)) else: if dists[nr][nc][nk] <= dists[r][c][key] + 1: continue dists[nr][nc][nk] = dists[r][c][key] + 1 q.append((nr, nc, nk)) gr, gc = find('G') d = min(dists[gr][gc]) if d == INF: print(-1) else: print(d)