結果
問題 |
No.3199 Key-Door Grid
|
ユーザー |
👑 |
提出日時 | 2025-07-11 21:59:28 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,397 ms / 3,000 ms |
コード長 | 1,592 bytes |
コンパイル時間 | 197 ms |
コンパイル使用メモリ | 82,216 KB |
実行使用メモリ | 139,888 KB |
最終ジャッジ日時 | 2025-07-11 22:00:02 |
合計ジャッジ時間 | 14,980 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
from collections import deque ways = [(-1, 0), (1, 0), (0, -1), (0, 1)] def solve(): H, W, M = map(int, input().split()) grid = [list(input()) for _ in range(H)] s_i, s_j = None, None for i in range(H): for j in range(W): if grid[i][j] == "S": s_i, s_j = i, j break else: continue break visited = [[[False] * W for _ in range(H)] for _ in range(M + 1)] visited[0][s_i][s_j] = True que = deque([(s_i, s_j, 0, 0)]) while que: curr_i, curr_j, key, dist = que.popleft() for di, dj in ways: next_i, next_j = curr_i + di, curr_j + dj if not (0 <= next_i < H and 0 <= next_j < W): continue if grid[next_i][next_j] == "#": continue if grid[next_i][next_j].islower() and grid[next_i][next_j] != chr(ord("a") + key - 1): continue if grid[next_i][next_j] == "G": print(dist + 1) return if grid[next_i][next_j].isdigit(): next_key = int(grid[next_i][next_j]) if not visited[next_key][next_i][next_j]: que.append((next_i, next_j, next_key, dist + 1)) visited[next_key][next_i][next_j] = True else: if not visited[key][next_i][next_j]: que.append((next_i, next_j, key, dist + 1)) visited[key][next_i][next_j] = True print(-1) if __name__ == "__main__": solve()