結果

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

ソースコード

diff # 

from collections import deque

h, w, m = map(int, input().split())
mp = [list(input().strip()) for _ in range(h)]
sx, sy = 0, 0
for i in range(h):
    for j in range(w):
        if mp[i][j] == 'S':
            sx, sy = i, j
            mp[i][j] = '.'
# 現在、i,jにいるかつ鍵kを持っているときの最短距離.
dist = [[[float("inf")]*(m+1) for _ in range(w)] for _ in range(h)]
que = deque()
dist[sx][sy][0] = 0
que.append((sx, sy, 0))
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
nums = set([str(i) for i in range(1, m+1)])
alps = set(chr(i) for i in range(ord('a'), ord('a') + m))
while que:
    x, y, k = que.popleft()
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if not (0 <= nx < h and 0 <= ny < w):
            continue
        if mp[nx][ny] == '#':
            continue
        if mp[nx][ny] == 'G':
            print(dist[x][y][k] + 1)
            exit()
        if mp[nx][ny] == '.':
            if dist[nx][ny][k] > dist[x][y][k] + 1:
                dist[nx][ny][k] = dist[x][y][k] + 1
                que.append((nx, ny, k))
        elif mp[nx][ny] in nums:
            nk = int(mp[nx][ny])
            if dist[nx][ny][nk] > dist[x][y][k] + 1:
                dist[nx][ny][nk] = dist[x][y][k] + 1
                que.append((nx, ny, nk))
        elif mp[nx][ny] in alps:
            if k == ord(mp[nx][ny]) - ord("a")+1:
                if dist[nx][ny][k] > dist[x][y][k] + 1:
                    dist[nx][ny][k] = dist[x][y][k] + 1
                    que.append((nx, ny, k))
print(-1)
0