結果
問題 |
No.3199 Key-Door Grid
|
ユーザー |
|
提出日時 | 2025-08-12 22:38:03 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,532 ms / 3,000 ms |
コード長 | 2,290 bytes |
コンパイル時間 | 477 ms |
コンパイル使用メモリ | 82,520 KB |
実行使用メモリ | 199,304 KB |
最終ジャッジ日時 | 2025-08-12 22:38:26 |
合計ジャッジ時間 | 21,947 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
from copy import deepcopy from collections import deque H, W, M = map(int, input().split()) A = [[]] alpha_num = {"a":1, "b":2, "c":3, "d":4, "e":5, "f":6, "g":7, "h":8, "i":9} num_set = set("123456789") for row in range(H): inp = list(input()) for col in range(W): if inp[col] in alpha_num: inp[col] = alpha_num[inp[col]] elif inp[col] in num_set: inp[col] = int(inp[col]) + 10 elif inp[col] == "S": s_row, s_col = row, col inp[col] = "." elif inp[col] == "G": g_row, g_col = row, col A[0].append(inp) for _ in range(M): A.append(deepcopy(A[-1])) vid_cost = [None for _ in range(H*W*(M+1))] s_vid = W*s_row + s_col vid_cost[s_vid] = 0 dif_rows = [-1, 1, 0, 0] dif_cols = [0, 0, -1, 1] q = deque() q.append((0, s_row, s_col)) while q: dim, now_row, now_col = q.popleft() now_vid = dim*H*W + W*now_row + now_col for dif_row, dif_col in zip(dif_rows, dif_cols): ne_row = now_row + dif_row ne_col = now_col + dif_col if 0 <= ne_row < H and 0 <= ne_col < W: if A[dim][ne_row][ne_col] == "#": continue elif A[dim][ne_row][ne_col] == ".": ne_vid = dim*H*W + W*ne_row + ne_col if vid_cost[ne_vid] == None: vid_cost[ne_vid] = vid_cost[now_vid] + 1 q.append((dim, ne_row, ne_col)) elif A[dim][ne_row][ne_col] == "G": print(vid_cost[now_vid] + 1) exit() elif 11<= A[dim][ne_row][ne_col]: ne_dim = A[dim][ne_row][ne_col] - 10 ne_vid = ne_dim*H*W + W*ne_row + ne_col if vid_cost[ne_vid] == None: vid_cost[ne_vid] = vid_cost[now_vid] + 1 q.append((ne_dim, ne_row, ne_col)) elif 1<= A[dim][ne_row][ne_col]: if dim == A[dim][ne_row][ne_col]: ne_vid = dim*H*W + W*ne_row + ne_col if vid_cost[ne_vid] == None: vid_cost[ne_vid] = vid_cost[now_vid] + 1 q.append((dim, ne_row, ne_col)) print(-1)