結果

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

ソースコード

diff # 

from collections import deque
import sys
input = sys.stdin.readline
H, W, M = map(int, input().split())
S = [input().strip() for _ in range(H)]
INF = 10**9
dist = [[[INF for _ in range(M+1)] for _ in range(W)] for _ in range(H)]
for i in range(H):
    for j in range(W):
        if S[i][j]=="S":
            sx, sy = i, j
        elif S[i][j]=="G":
            gx, gy = i, j
deq = deque()
deq.append((sx, sy, 0))
dist[sx][sy][0] = 0
dir = [(0, 1), (1, 0), (0, -1), (-1, 0)]
while deq:
    x, y, f = deq.popleft()
    for dx, dy in dir:
        nx = x+dx
        ny = y+dy
        if 0<=nx<H and 0<=ny<W:
            if S[nx][ny]=="." or S[nx][ny]=="S" or S[nx][ny]=="G":
                if dist[nx][ny][f] > dist[x][y][f]+1:
                    dist[nx][ny][f] = dist[x][y][f]+1
                    deq.append((nx, ny, f))
            elif "1"<=S[nx][ny]<="9":
                nf = int(S[nx][ny])
                if dist[nx][ny][nf] > dist[x][y][f]+1:
                    dist[nx][ny][nf] = dist[x][y][f]+1
                    deq.append((nx, ny, nf))
            elif "a"<=S[nx][ny]<="i":
                tmp = ord(S[nx][ny])-ord("a")+1
                if tmp==f:
                    if dist[nx][ny][f] > dist[x][y][f]+1:
                        dist[nx][ny][f] = dist[x][y][f]+1
                        deq.append((nx, ny, f))
ans = INF
for i in range(M+1):
    ans = min(ans, dist[gx][gy][i])
if ans==INF:
    print(-1)
else:
    print(ans)
0