結果

問題 No.3199 Key-Door Grid
コンテスト
ユーザー 三価スニウム
提出日時 2025-07-11 22:41:16
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 968 ms / 3,000 ms
コード長 1,504 bytes
コンパイル時間 531 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 136,700 KB
最終ジャッジ日時 2025-07-11 22:41:29
合計ジャッジ時間 13,369 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline().strip()

from collections import deque
def main():
    H, W, M = map(int, input().split())
    S = [input() for _ in range(H)]
    DOOR = [None] * M
    for i, line in enumerate(S):
        for j, cell in enumerate(line):
            if cell == 'S':
                START = W * i + j
            elif cell == 'G':
                GOAL = W * i + j
    DIRS = ((1, 0), (0, 1), (-1, 0), (0, -1))

    INF = 10**8
    dist = [[INF] * (M+1) for _ in range(H*W)]
    dist[START][0] = 0
    queue = deque([(START, 0)])

    while queue:
        c, k = queue.popleft()
        i, j = divmod(c, W)
        for di, dj in DIRS:
            ni = i + di
            nj = j + dj
            nc = W * ni + nj
            if 0 <= ni < H and 0 <= nj < W:
                if S[ni][nj] in ('.', 'S', 'G') and dist[nc][k] == INF:
                    queue.append((nc, k))
                    dist[nc][k] = dist[c][k] + 1
                elif S[ni][nj].isdigit() and dist[nc][int(S[ni][nj])] == INF:
                    queue.append((nc, int(S[ni][nj])))
                    dist[nc][int(S[ni][nj])] = dist[c][k] + 1
                elif ord('a') <= ord(S[ni][nj]) <= ord('z') and k == ord(S[ni][nj]) - ord('a') + 1 and dist[nc][k] == INF:
                    queue.append((nc, k))
                    dist[nc][k] = dist[c][k] + 1

    ans = min(dist[GOAL])
    print(ans) if ans < INF else print(-1)


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