概要

高橋君は警備ロボットがいる迷宮から、最短ターンで出口へ脱出できるかを判定する問題です。警備ロボットは高橋君の位置に応じて動くため、両者の動きをシミュレーションしながら探索を行う必要があります。

考察

この問題では、高橋君の動きだけでなく、それに応じて動く警備ロボットの動きも考える必要があります。単純な幅優先探索（BFS）では、同じマスに複数回訪れるような無駄な経路も含まれてしまうため、状態として「高橋君の位置」と「すべての警備ロボットの位置」を管理する必要があります。

さらに、警備ロボットの移動は高橋君の位置によって決まるため、高橋君が動いた後にロボットが動くという順序も重要です。ロボットの動きは決定的であり、マンハッタン距離と決められた優先順位に従って移動先が選ばれます。

また、制約が非常に小さい（\(N, M \leq 8\), \(K \leq 2\)）ため、全状態を探索することが可能であり、BFSによる全探索が有効です。

アルゴリズム

この問題は、状態付きの幅優先探索（BFS）を用いて解きます。

状態の定義

• ターン数
• 高橋君の位置 \((r, c)\)
• 各警備ロボットの位置（最大2つ）をタプルで持つ

探索の流れ

1. 初期状態（ターン1、高橋君の初期位置、警備ロボットの初期位置）をキューに追加し、訪問済み集合に登録。
2. キューから状態を取り出し、高橋君が移動可能なマスへ移動。
3. 移動後に警備ロボットに捕まる場合はその経路を破棄。
4. 出口に到達すればそのターン数を出力して終了。
5. 警備ロボットを動かした後にもう一度捕獲チェック。
6. 新しい状態（高橋君の新しい位置＋ロボットの新しい位置）が未訪問であれば、ターン数をインクリメントしてキューに追加。
7. キューが空になるまで繰り返し、到達できなければ -1 を出力。

警備ロボットの移動は、高橋君の新しい位置とのマンハッタン距離が最も小さくなる方向に、決められた優先順に従って移動させます。

計算量

グリッドサイズが最大 \(8 \times 8 = 64\) マス、警備ロボットが最大2体なので、ロボットの位置の組み合わせは高々 \(64^2 = 4096\) 通り。高橋君の位置も64通り。よって状態数はおおよそ \(64 \times 4096 = 262144\) 程度になり、十分にBFSで扱える範囲です。

• 時間計算量: \(O(NM \cdot (NM)^K \cdot 5)\) （5は高橋君の移動選択肢）
• 空間計算量: \(O(NM \cdot (NM)^K)\)

実装のポイント

• 座標系は0-indexに変換して扱う（入力は1-index）。

• 警備ロボットの移動関数では、マンハッタン距離が最小かつ優先順位が高いものを選ぶよう実装。

• BFSの状態にはターン数、プレイヤー位置、ロボット位置を含める。

• 同じ状態（プレイヤー位置＋ロボット位置）は再度探索しないように訪問済み集合で管理。

• キューには deque を使い、効率よく探索を行う。

  ソースコード

from collections import deque
import sys

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx]); idx += 1
    M = int(data[idx]); idx += 1
    K = int(data[idx]); idx += 1
    
    Sr = int(data[idx]) - 1; idx += 1
    Sc = int(data[idx]) - 1; idx += 1
    
    Gr = int(data[idx]) - 1; idx += 1
    Gc = int(data[idx]) - 1; idx += 1
    
    guards = []
    for _ in range(K):
        pr = int(data[idx]) - 1; idx += 1
        pc = int(data[idx]) - 1; idx += 1
        guards.append((pr, pc))
    
    grid = []
    for _ in range(N):
        grid.append(data[idx])
        idx += 1
    
    # Directions: up, down, left, right, stay
    DIRS = [(-1,0), (1,0), (0,-1), (0,1), (0,0)]
    DIR_ORDER = {'up':0, 'down':1, 'left':2, 'right':3, 'stay':4}
    
    def is_valid(r, c):
        return 0 <= r < N and 0 <= c < M and grid[r][c] == '.'
    
    def manhattan(r1, c1, r2, c2):
        return abs(r1-r2) + abs(c1-c2)
    
    def move_guard(gr, gc, tr, tc):
        # Possible moves
        candidates = []
        for i, (dr, dc) in enumerate(DIRS):
            nr, nc = gr + dr, gc + dc
            if is_valid(nr, nc):
                dist = manhattan(nr, nc, tr, tc)
                candidates.append((dist, i, nr, nc))
        if not candidates:
            return gr, gc
        candidates.sort(key=lambda x: (x[0], x[1]))
        return candidates[0][2], candidates[0][3]
    
    # BFS with state: (turn, player_r, player_c, guard_positions)
    # But since K<=2 and N,M<=8, we can represent guard positions as tuple
    # State: (turn, pr, pc, ((gr1,gc1), (gr2,gc2), ...))
    initial_state = (1, Sr, Sc, tuple(guards))
    queue = deque([initial_state])
    visited = set()
    visited.add((Sr, Sc, tuple(guards)))
    
    while queue:
        turn, pr, pc, guard_pos = queue.popleft()
        
        # Player possible moves
        player_moves = []
        for dr, dc in DIRS:
            nr, nc = pr + dr, pc + dc
            if is_valid(nr, nc):
                player_moves.append((nr, nc))
        
        for npr, npc in player_moves:
            # Capture check after player move
            caught1 = any((npr, npc) == gpos for gpos in guard_pos)
            if caught1:
                continue
            
            # Escape check
            if (npr, npc) == (Gr, Gc):
                print(turn)
                return
            
            # Guard moves
            new_guards = []
            for gr, gc in guard_pos:
                ng_r, ng_c = move_guard(gr, gc, npr, npc)
                new_guards.append((ng_r, ng_c))
            
            new_guard_tuple = tuple(new_guards)
            
            # Capture check after guard move
            caught2 = any((npr, npc) == gpos for gpos in new_guard_tuple)
            if caught2:
                continue
            
            # Check if this state has been visited
            state_key = (npr, npc, new_guard_tuple)
            if state_key in visited:
                continue
            visited.add(state_key)
            
            queue.append((turn+1, npr, npc, new_guard_tuple))
    
    print(-1)

if __name__ == "__main__":
    main()

---

この解説は qwen3-coder-480b によって生成されました。