結果

問題 No.3199 Key-Door Grid
コンテスト
ユーザー norioc
提出日時 2025-07-12 07:04:11
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,699 ms / 3,000 ms
コード長 1,624 bytes
コンパイル時間 328 ms
コンパイル使用メモリ 82,768 KB
実行使用メモリ 183,552 KB
最終ジャッジ日時 2025-09-08 10:08:18
合計ジャッジ時間 24,693 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import deque


def list3(a, b, c, *, val=0):
    return [[[val] * c for _ in range(b)] for _ in range(a)]


def neighbors4(r: int, c: int) -> list[tuple[int, int]]:
    res = []
    for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        nr = r + dr
        nc = c + dc
        if not (0 <= nr < H and 0 <= nc < W): continue
        res.append((nr, nc))

    return res


INF = 1 << 60
H, W, M = map(int, input().split())
S = []
for _ in range(H):
    S.append(list(input()))


def find(c):
    for i in range(H):
        for j in range(W):
            if S[i][j] == c:
                return i, j

    assert False


sr, sc = find('S')
dists = list3(H, W, 10, val=INF)
dists[sr][sc][0] = 0
q = deque([(sr, sc, 0)])
while q:
    r, c, key = q.popleft()
    for nr, nc in neighbors4(r, c):
        if S[nr][nc] == '#': continue

        nk = key
        if S[nr][nc].islower():
            a = ord(S[nr][nc]) - ord('a') + 1
            if nk != a: continue
            if dists[nr][nc][nk] <= dists[r][c][key] + 1: continue
            dists[nr][nc][nk] = dists[r][c][key] + 1
            q.append((nr, nc, nk))
        elif S[nr][nc].isdigit():
            nk = ord(S[nr][nc]) - ord('1') + 1
            if dists[nr][nc][nk] <= dists[r][c][key] + 1: continue
            dists[nr][nc][nk] = dists[r][c][key] + 1
            q.append((nr, nc, nk))
        else:
            if dists[nr][nc][nk] <= dists[r][c][key] + 1: continue
            dists[nr][nc][nk] = dists[r][c][key] + 1
            q.append((nr, nc, nk))

gr, gc = find('G')
d = min(dists[gr][gc])
if d == INF:
    print(-1)
else:
    print(d)
0