結果

問題 No.3199 Key-Door Grid
コンテスト
ユーザー kidodesu
提出日時 2025-07-11 21:45:14
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 612 ms / 3,000 ms
コード長 1,325 bytes
コンパイル時間 237 ms
コンパイル使用メモリ 81,664 KB
実行使用メモリ 120,404 KB
最終ジャッジ日時 2025-07-11 21:45:35
合計ジャッジ時間 9,374 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

diff # 

h, w, m = map(int, input().split())
S = [input() for _ in range(h)]
for y in range(h):
    for x in range(w):
        if S[y][x] == "S":
            sy, sx = y, x
        elif S[y][x] == "G":
            gy, gx = y, x

N = h * w
dp = [-1] * N * 10
dp[(sy*w+sx)*10] = 0
from collections import deque
dq = deque([(sy, sx, 0)])
dy = [0, 0, 1, -1]
dx = [1, -1, 0, 0]
while dq:
    y, x, k = dq.popleft()
    now = dp[(y*w+x)*10+k]
    for d in range(4):
        ny, nx = y + dy[d], x + dx[d]
        if 0 <= ny < h and 0 <= nx < w and S[ny][nx] != "#":
            if S[ny][nx] in "0123456789":
                a = int(S[ny][nx])
                if dp[(ny*w+nx)*10+a] == -1:
                    dp[(ny*w+nx)*10+a] = now + 1
                    dq.append((ny, nx, a))
            elif S[ny][nx] in "abcdefghi":
                a = ord(S[ny][nx]) - ord("a") + 1
                if a == k and dp[(ny*w+nx)*10+a] == -1:
                    dp[(ny*w+nx)*10+a] = now + 1
                    dq.append((ny, nx, a))
            else:
                if dp[(ny*w+nx)*10+k] == -1:
                    dp[(ny*w+nx)*10+k] = now + 1
                    dq.append((ny, nx, k))

ans = 1 << 30
for i in range(10):
    if dp[(gy*w+gx)*10+i] != -1:
        ans = min(ans, dp[(gy*w+gx)*10+i])

if ans == 1 << 30:
    print(-1)
else:
    print(ans)
0