結果

問題 No.3199 Key-Door Grid
コンテスト
ユーザー YY-otter
提出日時 2025-07-01 17:57:32
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,113 ms / 3,000 ms
コード長 1,604 bytes
コンパイル時間 521 ms
コンパイル使用メモリ 82,364 KB
実行使用メモリ 184,308 KB
最終ジャッジ日時 2025-07-11 05:02:26
合計ジャッジ時間 16,979 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def solve():
    H, W, M = map(int, sys.stdin.readline().split())
    grid = []
    start_pos, goal_pos = None, None
    for r in range(H):
        row = list(sys.stdin.readline().strip())
        for c in range(W):
            if row[c] == 'S': start_pos = (r, c)
            elif row[c] == 'G': goal_pos = (r, c)
        grid.append(row)

    INF = float('inf')
    # dist[r][c][key]: key=0は鍵なし, key=1..Mは鍵1..M
    dist = [[[INF] * (M + 1) for _ in range(W)] for _ in range(H)]
    q = deque()

    sr, sc = start_pos
    dist[sr][sc][0] = 0
    q.append((sr, sc, 0)) # r, c, key

    dr = [-1, 1, 0, 0]
    dc = [0, 0, -1, 1]

    while q:
        r, c, current_key = q.popleft()

        for i in range(4):
            nr, nc = r + dr[i], c + dc[i]

            if not (0 <= nr < H and 0 <= nc < W and grid[nr][nc] != '#'):
                continue
            
            cell = grid[nr][nc]
            
            # 扉のチェック
            if 'a' <= cell <= 'i':
                required_key = ord(cell) - ord('a') + 1
                if required_key != current_key:
                    continue

            # 次の鍵の状態
            next_key = current_key
            if '1' <= cell <= '9':
                next_key = int(cell)
            
            if dist[r][c][current_key] + 1 < dist[nr][nc][next_key]:
                dist[nr][nc][next_key] = dist[r][c][current_key] + 1
                q.append((nr, nc, next_key))

    gr, gc = goal_pos
    ans = min(dist[gr][gc])
    
    print(ans if ans != INF else -1)

solve()
0