結果

問題 No.3199 Key-Door Grid
コンテスト
ユーザー LyricalMaestro
提出日時 2025-10-22 23:52:03
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 871 ms / 3,000 ms
コード長 2,051 bytes
コンパイル時間 423 ms
コンパイル使用メモリ 82,592 KB
実行使用メモリ 124,124 KB
最終ジャッジ日時 2025-10-22 23:52:16
合計ジャッジ時間 12,876 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

diff # 

# https://yukicoder.me/problems/no/3213s

MAX_VALUE = 2 * 10 ** 18

from collections import deque

def main():
    H, W, M = map(int, input().split())
    S = []
    for _ in range(H):
        S.append(input())

    
    dist = [[[MAX_VALUE] * W for _ in range(H)] for _ in range(M + 1)]

    start = None
    goal = None
    for h in range(H):
        for w in range(W):
            if S[h][w] == "S":
                start =(h, w)
            if S[h][w] == "G":
                goal =(h ,w)

    queue = deque()
    queue.append((0, start[0], start[1]))

    dist[0][start[0]][start[1]] = 0
    while len(queue) > 0:
        state, h, w = queue.popleft()
        d = dist[state][h][w]

        for dh, dw in ((1, 0), (-1, 0), (0, -1), (0, 1)):
            new_h = dh + h 
            new_w = dw + w
            if 0 <= new_h < H and 0 <= new_w < W:
                if S[new_h][new_w] == "#":
                    continue
                
                if S[new_h][new_w] in (".", "S", "G"):
                    if dist[state][new_h][new_w] == MAX_VALUE:
                        dist[state][new_h][new_w] = d + 1
                        queue.append((state, new_h, new_w))
                elif S[new_h][new_w].isdigit():
                    new_state = int(S[new_h][new_w])
                    if dist[new_state][new_h][new_w] == MAX_VALUE:
                        dist[new_state][new_h][new_w] = d + 1
                        queue.append((new_state, new_h, new_w))
                elif S[new_h][new_w].isalpha() and S[new_h][new_w].islower():
                    if state ==  ord(S[new_h][new_w]) - ord("a") + 1:
                        if dist[state][new_h][new_w] == MAX_VALUE:
                            dist[state][new_h][new_w] = d + 1
                            queue.append((state, new_h, new_w))


    answer = MAX_VALUE
    for state in range(M + 1):
        answer = min(answer, dist[state][goal[0]][goal[1]])
    if answer == MAX_VALUE:
        print(-1)
    else:
        print(answer)









if __name__ == "__main__":
    main()
0