結果

問題 No.3199 Key-Door Grid
コンテスト
ユーザー timi
提出日時 2025-07-13 00:16:46
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 685 ms / 3,000 ms
コード長 1,071 bytes
コンパイル時間 404 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 121,600 KB
最終ジャッジ日時 2025-07-13 00:16:58
合計ジャッジ時間 11,044 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

diff # 

H,W,M=map(int, input().split())

S='123456789'
T='_abcdefghi'

A=[]
for i in range(H):
  s=input()
  A.append(s)
  for j in range(W):
    if s[j]=='S':
      sy,sx=i,j
    elif s[j]=='G':
      gy,gx=i,j
      
from collections import deque
d=deque()

dy,dx=[1,-1,0,0],[0,0,1,-1]

V=[[[-1]*W for _ in range(H)] for _ in range(10)]
V[0][sy][sx]=0
d.append((0,sy,sx))
while d:
  c,y,x=d.popleft()
  for i in range(4):
    ny,nx=y+dy[i],x+dx[i]
    if 0<=ny<H and 0<=nx<W and A[ny][nx]!='#':
      if A[ny][nx]=='.' or A[ny][nx]=='S' or A[ny][nx]=='G':
        if V[c][ny][nx]==-1:
          V[c][ny][nx]=V[c][y][x]+1
          d.append((c,ny,nx))
      elif A[ny][nx] in S:
        cc=int(A[ny][nx])
        if V[cc][ny][nx]==-1:
          V[cc][ny][nx]=V[c][y][x]+1
          d.append((cc,ny,nx))
      else:
        if A[ny][nx]==T[c]:
          if V[c][ny][nx]==-1:
            V[c][ny][nx]=V[c][y][x]+1
            d.append((c,ny,nx))
      
ans=10**10
for i in range(10):
  c=V[i][gy][gx]
  if c!=-1:
    ans=min(ans,c)

if ans==10**10:
  print(-1)
else:
  print(ans)
0