結果

問題 No.3199 Key-Door Grid
ユーザー miho-4
提出日時 2025-07-11 22:32:04
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,385 bytes
コンパイル時間 424 ms
コンパイル使用メモリ 81,868 KB
実行使用メモリ 53,476 KB
最終ジャッジ日時 2025-07-11 22:32:11
合計ジャッジ時間 4,950 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other TLE * 1 -- * 36
権限があれば一括ダウンロードができます

ソースコード

diff # 

#from collections import deque
import heapq

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

heap=[(0,sh,sw,0)]
while heap:
  d,h,w,k=heapq.heappop(heap)
  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
          heapq.heappush(heap,(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
          heapq.heappush(heap,(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
          heapq.heappush(heap,(d+1,h+dh,w+dw, nx ))
      elif L[h+dh][w+dw] in "SG":
        if dp[h][w][k]+1<dp[h+dh][w+dw][k]:
          dp[h+dh][w+dw][k]=dp[h][w][k]+1
          heapq.heappush(heap,(d+1,h+dh,w+dw,k))

ans=10**6
for k in range(M+1):
  ans=min(ans,dp[th][tw][k])
print(ans if ans<10**6 else -1)
0