結果
問題 |
No.3199 Key-Door Grid
|
ユーザー |
![]() |
提出日時 | 2025-07-11 22:46:39 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,095 ms / 3,000 ms |
コード長 | 1,643 bytes |
コンパイル時間 | 272 ms |
コンパイル使用メモリ | 82,168 KB |
実行使用メモリ | 150,028 KB |
最終ジャッジ日時 | 2025-07-11 22:46:57 |
合計ジャッジ時間 | 14,744 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
from string import ascii_lowercase as abc abc = "*"+abc def solve(H, W, M, grid): dp = full((M+1, H, W), INF) def get(ch): for i in range(H): for j in range(W): if grid[i][j] == ch: return i, j assert False si, sj = get("S") ti, tj = get("G") grid[si] = grid[si].replace("S", ".") grid[ti] = grid[ti].replace("G", ".") dp[0][si][sj] = 0 from collections import deque Q = deque([(0, si, sj)]) def relax(nm, ni, nj, dist): ndist = dist + 1 if dp[nm][ni][nj] <= ndist: return dp[nm][ni][nj] = ndist Q.append((nm, ni, nj)) while Q: m, i, j = Q.popleft() dist = dp[m][i][j] for di, dj in DIR4: ni, nj = i+di, j+dj if not (0 <= ni < H and 0 <= nj < W): continue nch = grid[ni][nj] if nch == "*": continue if "a" <= nch <= "z": id = ord(nch) - ord("a") + 1 if id == m: relax(m, ni, nj, dist) if "1" <= nch <= "9": nm = int(nch) relax(nm, ni, nj, dist) if nch == ".": relax(m, ni, nj, dist) res = min(dp[m][ti][tj] for m in range(M+1)) if res == INF: return -1 return res DIR4 = [(1, 0), (0, 1), (-1, 0), (0, -1)] import typing INF = typing.cast(int, float("INF")) def full(shape: tuple[int, ...], fill_value): assert len(shape) >= 1 if len(shape) == 1: return [fill_value] * shape[0] return [full(shape[1:], fill_value) for _ in range(shape[0])] H, W, M = map(int, input().split()) grid = [input() for _ in range(H)] ans = solve(H, W, M, grid) print(ans)