結果

問題 No.3199 Key-Door Grid
ユーザー ルク
提出日時 2025-07-11 21:44:27
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,033 bytes
コンパイル時間 615 ms
コンパイル使用メモリ 81,664 KB
実行使用メモリ 300,624 KB
最終ジャッジ日時 2025-07-11 21:44:40
合計ジャッジ時間 5,004 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other TLE * 1 -- * 36
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import deque

h, w, m = map(int, input().split())
mp = [input() for _ in range(h)]
sx, sy = 0, 0
gx, gy = 0, 0
for i in range(h):
    for j in range(w):
        if mp[i][j] == 'S':
            sx, sy = i, j
            mp[i] = mp[i][:j] + '.' + mp[i][j+1:]
        elif mp[i][j] == 'G':
            gx, gy = i, j
            mp[i] = mp[i][:j] + '.' + mp[i][j+1:]
que = deque([(sx, sy, 0, 0)])  # (x,y,key,dist)
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
visited = [[(-1, 0)]*w for _ in range(h)]  # (x,y) -> key
visited[sx][sy] = (0, 0)
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, key, dist = que.popleft()
    if (x, y) == (gx, gy):
        print(dist)
        exit()
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < h and 0 <= ny < w:
            if mp[nx][ny] == '#':
                continue
            if mp[nx][ny] == '.':
                if visited[nx][ny][0] != key and visited[nx][ny][1] < dist + 1:
                    visited[nx][ny] = (key, dist + 1)
                    que.append((nx, ny, key, dist + 1))
            elif mp[nx][ny] in nums:
                new_key = ord(mp[nx][ny]) - ord('0')
                if visited[nx][ny][0] != new_key and visited[nx][ny][1] < dist + 1:
                    visited[nx][ny] = (new_key, dist + 1)
                    que.append((nx, ny, new_key, dist + 1))
            elif mp[nx][ny] in alps:
                if key == 0:
                    continue
                if key == ord(mp[nx][ny]) - ord('a') + 1:
                    if visited[nx][ny] != key and visited[nx][ny][1] < dist + 1:
                        visited[nx][ny] = (key, dist + 1)
                        que.append((nx, ny, key, dist + 1))
            elif mp[nx][ny] == 'G':
                if visited[nx][ny] != key and visited[nx][ny][1] < dist + 1:
                    visited[nx][ny] = (key, dist + 1)
                    que.append((nx, ny, key, dist + 1))
print(-1)
0