結果

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

ソースコード

diff # 

from collections import deque

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


def solve():
    H, W, M = map(int, input().split())
    grid = [list(input()) for _ in range(H)]

    s_i, s_j = None, None
    for i in range(H):
        for j in range(W):
            if grid[i][j] == "S":
                s_i, s_j = i, j
                break
        else:
            continue
        break

    visited = [[[False] * W for _ in range(H)] for _ in range(M + 1)]
    visited[0][s_i][s_j] = True

    que = deque([(s_i, s_j, 0, 0)])

    while que:
        curr_i, curr_j, key, dist = que.popleft()

        for di, dj in ways:
            next_i, next_j = curr_i + di, curr_j + dj

            if not (0 <= next_i < H and 0 <= next_j < W):
                continue

            if grid[next_i][next_j] == "#":
                continue

            if grid[next_i][next_j].islower() and grid[next_i][next_j] != chr(ord("a") + key - 1):
                continue

            if grid[next_i][next_j] == "G":
                print(dist + 1)
                return

            if grid[next_i][next_j].isdigit():
                next_key = int(grid[next_i][next_j])

                if not visited[next_key][next_i][next_j]:
                    que.append((next_i, next_j, next_key, dist + 1))
                    visited[next_key][next_i][next_j] = True
            else:
                if not visited[key][next_i][next_j]:
                    que.append((next_i, next_j, key, dist + 1))
                    visited[key][next_i][next_j] = True

    print(-1)


if __name__ == "__main__":
    solve()
0