結果

問題 No.3199 Key-Door Grid
ユーザー miho-4
提出日時 2025-07-11 22:36:12
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 909 ms / 3,000 ms
コード長 1,291 bytes
コンパイル時間 400 ms
コンパイル使用メモリ 82,708 KB
実行使用メモリ 138,528 KB
最終ジャッジ日時 2025-07-11 22:36:26
合計ジャッジ時間 14,023 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import deque

key={"a":1,"b":2,"c":3,"d":4,"e":5,"f":6,"g":7,"h":8,"i":9}
dhw=[(1,0),(-1,0),(0,1),(0,-1)]
H,W,M=map(int,input().split())
L=[str(input()) for _ in range(H)]

dp=[[[10**6]*(M+1) for w in range(W)] for h in range(H)]

for h in range(H):
  for w in range(W):
    if L[h][w]=="S":
      sh,sw=h,w
    if L[h][w]=="G":
      th,tw=h,w
      
dp[sh][sw][0]=0

q=deque([(0,sh,sw,0)])
while q:
  d,h,w,k=q.popleft()
  for dh,dw in dhw:
    if 0<=h+dh<H and 0<=w+dw<W:
      if L[h+dh][w+dw]=="#":continue
      if L[h+dh][w+dw]==".":
        if dp[h][w][k]+1<dp[h+dh][w+dw][k]:
          dp[h+dh][w+dw][k]=dp[h][w][k]+1
          q.append((d+1,h+dh,w+dw,k))
      elif L[h+dh][w+dw] in key and k==key[L[h+dh][w+dw]]:
        if dp[h][w][k]+1<dp[h+dh][w+dw][k]:
          dp[h+dh][w+dw][k]=dp[h][w][k]+1
          q.append((d+1,h+dh,w+dw,k))
      elif L[h+dh][w+dw] in "123456789":
        nx=int(L[h+dh][w+dw])
        if dp[h][w][k]+1<dp[h+dh][w+dw][ nx ]:
          dp[h+dh][w+dw][ nx ]=dp[h][w][k]+1
          q.append((d+1,h+dh,w+dw, nx ))
      elif L[h+dh][w+dw] =="S":
        if dp[h][w][k]+1<dp[h+dh][w+dw][k]:
          dp[h+dh][w+dw][k]=dp[h][w][k]+1
          q.append((d+1,h+dh,w+dw,k))
      elif L[h+dh][w+dw]=="G":
        exit(print(d+1))

print(-1)
0