結果
問題 |
No.3199 Key-Door Grid
|
ユーザー |
![]() |
提出日時 | 2025-07-13 00:16:46 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 685 ms / 3,000 ms |
コード長 | 1,071 bytes |
コンパイル時間 | 404 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 121,600 KB |
最終ジャッジ日時 | 2025-07-13 00:16:58 |
合計ジャッジ時間 | 11,044 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
H,W,M=map(int, input().split()) S='123456789' T='_abcdefghi' A=[] for i in range(H): s=input() A.append(s) for j in range(W): if s[j]=='S': sy,sx=i,j elif s[j]=='G': gy,gx=i,j from collections import deque d=deque() dy,dx=[1,-1,0,0],[0,0,1,-1] V=[[[-1]*W for _ in range(H)] for _ in range(10)] V[0][sy][sx]=0 d.append((0,sy,sx)) while d: c,y,x=d.popleft() for i in range(4): ny,nx=y+dy[i],x+dx[i] if 0<=ny<H and 0<=nx<W and A[ny][nx]!='#': if A[ny][nx]=='.' or A[ny][nx]=='S' or A[ny][nx]=='G': if V[c][ny][nx]==-1: V[c][ny][nx]=V[c][y][x]+1 d.append((c,ny,nx)) elif A[ny][nx] in S: cc=int(A[ny][nx]) if V[cc][ny][nx]==-1: V[cc][ny][nx]=V[c][y][x]+1 d.append((cc,ny,nx)) else: if A[ny][nx]==T[c]: if V[c][ny][nx]==-1: V[c][ny][nx]=V[c][y][x]+1 d.append((c,ny,nx)) ans=10**10 for i in range(10): c=V[i][gy][gx] if c!=-1: ans=min(ans,c) if ans==10**10: print(-1) else: print(ans)