結果

問題 No.3199 Key-Door Grid
ユーザー moon17
提出日時 2025-07-11 21:47:24
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 913 ms / 3,000 ms
コード長 759 bytes
コンパイル時間 493 ms
コンパイル使用メモリ 82,916 KB
実行使用メモリ 140,004 KB
最終ジャッジ日時 2025-07-11 21:47:45
合計ジャッジ時間 12,862 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import*
h,w,m=map(int,input().split())
s=[input()for _ in range(h)]
for i in range(h):
  for j in range(w):
    if s[i][j]=='S':
      si,sj=i,j
    if s[i][j]=='G':
      gi,gj=i,j
q=deque([(0,si*w+sj)])
INF=1<<60
t=[[INF]*(m+1)for _ in range(h*w)]
t[si*w+sj][0]=0
while q:
  c,p=q.popleft()
  i,j=p//w,p%w
  for di,dj in(-1,0),(1,0),(0,1),(0,-1):
    ni,nj=i+di,j+dj
    if not(0<=ni<h and 0<=nj<w):
      continue
    np=ni*w+nj
    nc=c
    if s[ni][nj]=='#':
      continue
    if '1'<=s[ni][nj]<='9':
      nc=int(s[ni][nj])
    if 'a'<=s[ni][nj]<='i':
      if nc!=ord(s[ni][nj])-ord('a')+1:
        continue
    if t[np][nc]<INF:
      continue
    t[np][nc]=t[p][c]+1
    q+=(nc,np),
ans=min(t[gi*w+gj])
print([-1,ans][ans<INF])
0