結果
問題 |
No.3199 Key-Door Grid
|
ユーザー |
![]() |
提出日時 | 2025-07-11 23:13:23 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 793 ms / 3,000 ms |
コード長 | 1,486 bytes |
コンパイル時間 | 410 ms |
コンパイル使用メモリ | 81,912 KB |
実行使用メモリ | 126,368 KB |
最終ジャッジ日時 | 2025-07-11 23:13:34 |
合計ジャッジ時間 | 10,748 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
import sys input = sys.stdin.readline from collections import deque H,W,M=map(int,input().split()) MAP=[input().strip() for i in range(H)] DP=[[[1<<60]*W for i in range(H)] for j in range(10)] Q=deque() for i in range(H): for j in range(W): if MAP[i][j]=="S": DP[0][i][j]=0 Q.append((0,i,j)) while Q: #print(Q) kk,x,y=Q.popleft() now=DP[kk][x][y] for z,w in [(x+1,y),(x-1,y),(x,y+1),(x,y-1)]: if 0<=z<H and 0<=w<W: if MAP[z][w]=="#": continue #print(MAP[z][w]) if 49<=ord(MAP[z][w])<=57: key=ord(MAP[z][w])-48 if DP[key][z][w]>now+1: DP[key][z][w]=now+1 Q.append((key,z,w)) elif 97<=ord(MAP[z][w])<=122: key=ord(MAP[z][w])-96 if kk==key: if DP[key][z][w]>now+1: DP[key][z][w]=now+1 Q.append((key,z,w)) else: if DP[kk][z][w]>now+1: DP[kk][z][w]=now+1 Q.append((kk,z,w)) ANS=1<<60 for i in range(H): for j in range(W): if MAP[i][j]=="G": for kk in range(10): ANS=min(ANS,DP[kk][i][j]) if ANS>10**6: print(-1) else: print(ANS)