概要

高橋君が警備ロボットのいる迷宮から脱出する問題で、各ターンで高橋君とロボットが交互に移動し、捕獲判定や脱出判定が行われる。最適な行動で脱出できる最小ターン数を求める。

考察

迷宮のサイズが最大8×8と小さく、警備ロボットの数も最大2体と少ないため、状態空間探索が可能。状態は（高橋君の位置, 全ロボットの位置）の組で表せ、状態数は高々\((8 \times 8) \times (8 \times 8)^K = 64 \times 64^K\)となり、K=2でも約26万状態程度に収まる。各状態からの遷移は高橋君の移動方向5通りを試せばよく、幅優先探索で最小ターン数を求められる。

アルゴリズム

幅優先探索(BFS)を用いる。状態を（高橋君の行, 高橋君の列, ロボット位置のタプル）で表現し、各状態から以下の手順で遷移を生成する： 1. 高橋君が上下左右または停止の5通りを試行 2. 移動先が壁ならスキップ 3. 移動後、ロボットと同じマスにいないか捕獲判定1 4. 出口なら脱出成功としてターン数を返す 5. ロボットを移動させ（移動ルールに従い高橋君に近づくように移動）、捕獲判定2 6. 新しい状態が未訪問ならキューに追加

ロボットの移動ルールは、移動可能な候補の中から高橋君とのマンハッタン距離が最小で、同距離なら上・下・左・右・停止の優先順位で選択する。

計算量

• 時間計算量: \(O((N \times M)^{K+1} \times 5)\)
• 空間計算量: \(O((N \times M)^{K+1})\)

実装のポイント

• 状態の同一性判定のためにロボット位置をタプルで保持

• ロボットの移動関数で、移動可能な全候補を列挙し距離計算と優先順位で選択

• 各ターンで2回の捕獲判定を正しい順序で実施

• グリッド座標が1-indexedなので、0-indexedに変換してアクセス

  ソースコード

import sys
from collections import deque

def main():
    data = sys.stdin.read().splitlines()
    if not data:
        print(-1)
        return
        
    first_line = data[0].split()
    N = int(first_line[0])
    M = int(first_line[1])
    K = int(first_line[2])
    S_r, S_c = map(int, data[1].split())
    G_r, G_c = map(int, data[2].split())
    robots = []
    idx = 3
    for i in range(K):
        r, c = map(int, data[idx].split())
        robots.append((r, c))
        idx += 1
        
    grid = []
    for i in range(N):
        grid.append(data[idx].strip())
        idx += 1
        
    dirs = [(-1,0), (1,0), (0,-1), (0,1), (0,0)]
    dir_names = ['上', '下', '左', '右', 'とどまる']
    
    def manhattan(r1, c1, r2, c2):
        return abs(r1 - r2) + abs(c1 - c2)
        
    def get_robot_move(pr, pc, h_r, h_c):
        candidates = []
        for dr, dc in dirs:
            nr = pr + dr
            nc = pc + dc
            if 1 <= nr <= N and 1 <= nc <= M and grid[nr-1][nc-1] == '.':
                candidates.append((nr, nc))
        best_dist = float('inf')
        best_move = None
        for cand in candidates:
            d = manhattan(cand[0], cand[1], h_r, h_c)
            if d < best_dist:
                best_dist = d
                best_move = cand
        return best_move
        
    def simulate_robots(robots_pos, h_r, h_c):
        new_robots = []
        for r_pos in robots_pos:
            new_pos = get_robot_move(r_pos[0], r_pos[1], h_r, h_c)
            new_robots.append(new_pos)
        return new_robots
        
    visited = set()
    q = deque()
    start_state = (S_r, S_c, tuple(robots))
    visited.add(start_state)
    q.append((0, S_r, S_c, robots))
    
    while q:
        turn, r, c, robots_state = q.popleft()
        if r == G_r and c == G_c:
            print(turn)
            return
            
        for dr, dc in dirs:
            nr = r + dr
            nc = c + dc
            if 1 <= nr <= N and 1 <= nc <= M and grid[nr-1][nc-1] == '.':
                new_robots_after_human = list(robots_state)
                captured1 = False
                for rob in new_robots_after_human:
                    if nr == rob[0] and nc == rob[1]:
                        captured1 = True
                        break
                if captured1:
                    continue
                    
                if nr == G_r and nc == G_c:
                    print(turn+1)
                    return
                    
                new_robots_after_move = simulate_robots(new_robots_after_human, nr, nc)
                captured2 = False
                for rob in new_robots_after_move:
                    if nr == rob[0] and nc == rob[1]:
                        captured2 = True
                        break
                if captured2:
                    continue
                    
                new_state = (nr, nc, tuple(new_robots_after_move))
                if new_state not in visited:
                    visited.add(new_state)
                    q.append((turn+1, nr, nc, new_robots_after_move))
                    
    print(-1)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。