結果

問題 No.3199 Key-Door Grid
コンテスト
ユーザー むつある
提出日時 2025-07-11 21:48:12
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 945 ms / 3,000 ms
コード長 1,088 bytes
コンパイル時間 331 ms
コンパイル使用メモリ 81,804 KB
実行使用メモリ 150,436 KB
最終ジャッジ日時 2025-07-11 21:48:33
合計ジャッジ時間 13,503 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import deque

h,w,m=map(int,input().split())
s=[list(input()) for _ in range(h)]

for i in range(h):
  for j in range(w):
    if s[i][j]=='S':
      st=[i,j]
    elif s[i][j]=="G":
      go=[i,j]
     
inf=10**18      
dp=[[[inf]*11 for _ in range(w)] for _ in range(h)]
dp[st[0]][st[1]][0]=0

s[st[0]][st[1]]="."
s[go[0]][go[1]]="."

dq=deque([(st[0],st[1],0)])
dir=[0,1,0,-1]

num=[str(i) for i in range(10)]

while dq:
  x,y,k=dq.popleft()
  now=dp[x][y][k]
  for i in range(4):
    p,q=x+dir[i],y+dir[i^1]
    if 0<=p<h and 0<=q<w:
      if s[p][q]=="#":
        continue
      if s[p][q]==".":
        if dp[p][q][k]>now+1:
          dp[p][q][k]=now+1
          dq.append((p,q,k))
      elif s[p][q] in num:
        v=int(s[p][q])
        if dp[p][q][v]>now+1:
          dp[p][q][v]=now+1
          dq.append((p,q,v))
      else:
        if ord(s[p][q])-ord('a')+1==k:
          if dp[p][q][k]>now+1:
            dp[p][q][k]=now+1
            dq.append((p,q,k))
            
ans=min(dp[go[0]][go[1]])

if ans==inf:
  print(-1)
else:
  print(ans)
0