結果

問題 No.3199 Key-Door Grid
コンテスト
ユーザー dp_ijk
提出日時 2025-07-11 22:46:39
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,095 ms / 3,000 ms
コード長 1,643 bytes
コンパイル時間 272 ms
コンパイル使用メモリ 82,168 KB
実行使用メモリ 150,028 KB
最終ジャッジ日時 2025-07-11 22:46:57
合計ジャッジ時間 14,744 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

diff # 

from string import ascii_lowercase as abc
abc = "*"+abc

def solve(H, W, M, grid):
   dp = full((M+1, H, W), INF)
   def get(ch):
      for i in range(H):
         for j in range(W):
            if grid[i][j] == ch:
               return i, j
      assert False
   si, sj = get("S")
   ti, tj = get("G")

   grid[si] = grid[si].replace("S", ".")
   grid[ti] = grid[ti].replace("G", ".")

   dp[0][si][sj] = 0
   from collections import deque
   Q = deque([(0, si, sj)])

   def relax(nm, ni, nj, dist):
      ndist = dist + 1
      if dp[nm][ni][nj] <= ndist: return
      dp[nm][ni][nj] = ndist
      Q.append((nm, ni, nj))

   while Q:
      m, i, j = Q.popleft()
      dist = dp[m][i][j]
      for di, dj in DIR4:
         ni, nj = i+di, j+dj
         if not (0 <= ni < H and 0 <= nj < W): continue
         nch = grid[ni][nj]
         if nch == "*": continue
         if "a" <= nch <= "z":
            id = ord(nch) - ord("a") + 1
            if id == m:
               relax(m, ni, nj, dist)
         if "1" <= nch <= "9":
            nm = int(nch)
            relax(nm, ni, nj, dist)
         if nch == ".":
            relax(m, ni, nj, dist)

   res = min(dp[m][ti][tj] for m in range(M+1))
   if res == INF:
      return -1
   return res


DIR4 = [(1, 0), (0, 1), (-1, 0), (0, -1)]

import typing
INF = typing.cast(int, float("INF"))
def full(shape: tuple[int, ...], fill_value):
   assert len(shape) >= 1
   if len(shape) == 1: return [fill_value] * shape[0]
   return [full(shape[1:], fill_value) for _ in range(shape[0])]
H, W, M = map(int, input().split())
grid = [input() for _ in range(H)]

ans = solve(H, W, M, grid)
print(ans)
0