結果
問題 |
No.3199 Key-Door Grid
|
ユーザー |
|
提出日時 | 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 |
ソースコード
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)