結果

問題 No.3199 Key-Door Grid
コンテスト
ユーザー detteiuu
提出日時 2025-07-11 21:41:01
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 805 ms / 3,000 ms
コード長 1,333 bytes
コンパイル時間 429 ms
コンパイル使用メモリ 82,296 KB
実行使用メモリ 130,560 KB
最終ジャッジ日時 2025-07-11 21:41:30
合計ジャッジ時間 11,061 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import deque

H, W, M = map(int, input().split())
S = [list(input()) for _ in range(H)]

def code(s):
    return ord(s)-ord("a")
def codeR(n):
    return chr(ord("a")+n)

sh, sw = -1, -1
for i in range(H):
    for j in range(W):
        if S[i][j] == "S":
            sh, sw = i, j

que = deque()
que.append((sh, sw, 0))
visited = [[[-1]*W for _ in range(H)] for _ in range(M+1)]
visited[0][sh][sw] = 0
direction = [(-1,0),(0,1),(1,0),(0,-1)]
while que:
    h, w, k = que.popleft()
    if S[h][w] == "G":
        print(visited[k][h][w])
        break
    for dh, dw in direction:
        nh, nw = h+dh, w+dw
        if 0<=nh<H and 0<=nw<W and S[nh][nw] != "#":
            if S[nh][nw] in [".", "S", "G"]:
                if visited[k][nh][nw] == -1:
                    visited[k][nh][nw] = visited[k][h][w]+1
                    que.append((nh, nw, k))
            elif S[nh][nw].isdigit():
                nk = int(S[nh][nw])
                if visited[nk][nh][nw] == -1:
                    visited[nk][nh][nw] = visited[k][h][w]+1
                    que.append((nh, nw, nk))
            else:
                a = code(S[nh][nw])+1
                if a == k and visited[k][nh][nw] == -1:
                    visited[k][nh][nw] = visited[k][h][w]+1
                    que.append((nh, nw, k))
else:
    print(-1)
0