結果

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

ソースコード

diff # 

H, W, M = map(int, input().split())
S = [input() for _ in range(H)]
si = sj = -1
gi = gj = -1
for i in range(H):
    for j in range(W):
        if S[i][j] == 'S':
            si, sj = i, j
        elif S[i][j] == 'G':
            gi, gj = i, j

from collections import deque

dp = [[[-1] * W for _ in range(H)] for _ in range(M + 1)]
dp[0][si][sj] = 0
que = deque([(0, si, sj)])
di, dj = [1, 0, -1, 0], [0, 1, 0, -1]
while que:
    m, i, j = que.popleft()
    for d in range(4):
        ni, nj = i + di[d], j + dj[d]
        if 0 <= ni < H and 0 <= nj < W and S[ni][nj] != '#':
            if S[ni][nj].isnumeric():
                # 鍵
                nm = int(S[ni][nj])
            elif S[ni][nj].isalpha() and S[ni][nj].islower():
                if ord(S[ni][nj]) == ord('a') + m - 1:
                    # 扉
                    nm = m
                else:
                    continue
            else:
                nm = m
            
            if dp[nm][ni][nj] == -1:
                dp[nm][ni][nj] = dp[m][i][j] + 1
                que.append((nm, ni, nj))

ans = -1
for m in range(M + 1):
    if dp[m][gi][gj] != -1:
        if ans == -1 or ans > dp[m][gi][gj]:
            ans = dp[m][gi][gj]
print(ans)
0