結果

問題 No.3199 Key-Door Grid
コンテスト
ユーザー u_kun
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

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)
0