結果

問題 No.3199 Key-Door Grid
ユーザー miho-4
提出日時 2025-07-11 22:33:54
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,356 bytes
コンパイル時間 361 ms
コンパイル使用メモリ 81,468 KB
実行使用メモリ 53,956 KB
最終ジャッジ日時 2025-07-11 22:34:00
合計ジャッジ時間 5,435 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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] =="S":
        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]=="G":
        exit(print(d+1))

print(-1)
0