概要

\(N \times M\) のグリッド迷宮で、最大2体の警備ロボットを避けながらスタートからゴールへ最短ターンで到達できるかを判定する問題です。ロボットの動きは高橋君の位置に基づいて決定的に決まるため、状態をBFS（幅優先探索）で探索します。

考察

重要な気づき

1. ロボットの動きは決定的: 各ターンで高橋君の移動後の位置が決まれば、ロボットの移動先は一意に決まります（マンハッタン距離最小 → 優先順位で一意）。つまり、ゲームの状態遷移は高橋君の選択のみに依存します。

2. 状態の定義: ある時点のゲーム状況は「高橋君の位置」と「全ロボットの位置」で完全に記述できます。同じ状態に再び到達した場合、それ以降の探索は無駄なのでスキップできます。

3. 状態数の見積もり: グリッドのマス数は最大 \(8 \times 8 = 64\)、ロボットは最大2体なので、状態数は最大 \(64^3 = 262144\) 程度です。これはBFSで十分に探索可能です。

素朴なアプローチが通る理由

制約が \(N, M \leq 8\)、\(K \leq 2\) と小さいため、全状態をBFSで探索しても十分高速です。状態の再訪を防ぐことで無限ループも回避できます。

アルゴリズム

BFS（幅優先探索） を用いて最短ターン数を求めます。

1. 状態: (高橋君の位置, ロボット1の位置, ロボット2の位置) をタプルで管理（\(K < 2\) の場合は対応するロボットが存在しないだけ）。
2. 初期状態: 入力で与えられた各初期位置。
3. 遷移: 高橋君の5つの行動（上・下・左・右・留まる）それぞれについて：
   • 移動先が通路かチェック
   • 捕獲判定1: 移動後に既存のロボット位置と被っていたらその行動は不可
   • 脱出判定: ゴールに到達していれば答えを出力
   • ロボット移動: 各ロボットについて、5方向の候補からマンハッタン距離が最小のもの（タイブレークは上→下→左→右→留まるの優先順位）を選択
   • 捕獲判定2: ロボット移動後に被っていたらその行動は不可
   • 新状態が未訪問なら、キューに追加
4. 終了条件: ゴール到達ならそのターン番号を出力。キューが空になったら -1。

ロボットの移動決定の具体例

ロボットが \((3, 3)\)、高橋君が \((1, 3)\) にいる場合： - 上 \((2, 3)\): 距離 \(|2-1|+|3-3|=1\) - 下 \((4, 3)\): 距離 \(|4-1|+|3-3|=3\) - 留まり \((3, 3)\): 距離 \(|3-1|+|3-3|=2\)

→ 距離1が最小なので上 \((2, 3)\) に移動。

計算量

• 時間計算量: \(O(V \cdot 5)\) ここで \(V = (NM)^{K+1}\) は状態数。\(N=M=8, K=2\) のとき \(V = 64^3 = 262144\) で、各状態で5方向を試すので約 \(1.3 \times 10^6\) 回の遷移処理。
• 空間計算量: \(O(V)\)（訪問済み集合とキューの分）

実装のポイント

• 各マスの位置を r * M + c の1次元インデックスで管理すると、状態のタプル生成やハッシュが高速になります。

• ロボットの移動関数は、5方向を優先順位順（上→下→左→右→留まる）にループし、最初に見つけた最小距離の候補を採用すればタイブレークが自然に処理されます。

• BFSなので最初にゴールに到達した時点のターン数が最小であることが保証されます。

• 同じ状態を2度訪問しないことで、無限ループ（永遠に脱出できないケース）も正しく -1 と判定できます。

  ソースコード

import sys
from collections import deque

def solve():
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    K = int(input_data[idx]); idx += 1
    Sr = int(input_data[idx])-1; idx += 1
    Sc = int(input_data[idx])-1; idx += 1
    Gr = int(input_data[idx])-1; idx += 1
    Gc = int(input_data[idx])-1; idx += 1
    
    robots = []
    for i in range(K):
        pr = int(input_data[idx])-1; idx += 1
        pc = int(input_data[idx])-1; idx += 1
        robots.append((pr, pc))
    
    grid = []
    for i in range(N):
        grid.append(input_data[idx]); idx += 1
    
    # Directions: up, down, left, right, stay (priority order for robots)
    # For robot tie-breaking: up > down > left > right > stay
    robot_dirs = [(-1, 0), (1, 0), (0, -1), (0, 1), (0, 0)]
    # For Takahashi: up, down, left, right, stay
    player_dirs = [(-1, 0), (1, 0), (0, -1), (0, 1), (0, 0)]
    
    def robot_move(robot_r, robot_c, player_r, player_c):
        """Determine robot's next position given player's current position after player moves."""
        best_dist = float('inf')
        best_move = (robot_r, robot_c)
        for dr, dc in robot_dirs:
            nr, nc = robot_r + dr, robot_c + dc
            if 0 <= nr < N and 0 <= nc < M and grid[nr][nc] == '.':
                dist = abs(nr - player_r) + abs(nc - player_c)
                if dist < best_dist:
                    best_dist = dist
                    best_move = (nr, nc)
        return best_move
    
    # State: (player_r, player_c, robot1_r, robot1_c, robot2_r, robot2_c, ...)
    # Encode as tuple for hashing
    
    # Number of cells
    def encode_pos(r, c):
        return r * M + c
    
    def decode_pos(v):
        return v // M, v % M
    
    # State: (player_pos, robot_pos_0, robot_pos_1, ..., robot_pos_{K-1})
    # Each pos encoded as r*M+c
    
    initial_robot_state = tuple(encode_pos(r, c) for r, c in robots)
    initial_state = (encode_pos(Sr, Sc),) + initial_robot_state
    
    # BFS
    visited = set()
    visited.add(initial_state)
    queue = deque()
    queue.append((initial_state, 0))  # state, turn (0 means no turn executed yet)
    
    while queue:
        state, turn = queue.popleft()
        player_pos = state[0]
        pr, pc = decode_pos(player_pos)
        robot_positions = state[1:]
        
        # Try all 5 moves for player
        for dpr, dpc in player_dirs:
            npr, npc = pr + dpr, pc + dpc
            if not (0 <= npr < N and 0 <= npc < M and grid[npr][npc] == '.'):
                continue
            
            new_turn = turn + 1
            new_player_pos = encode_pos(npr, npc)
            
            # Capture check 1: any robot at player's new position?
            captured = False
            for rp in robot_positions:
                if rp == new_player_pos:
                    captured = True
                    break
            if captured:
                continue
            
            # Escape check: player at goal?
            if npr == Gr and npc == Gc:
                print(new_turn)
                return
            
            # Robot movement
            new_robots = []
            for rp in robot_positions:
                rr, rc = decode_pos(rp)
                nrr, nrc = robot_move(rr, rc, npr, npc)
                new_robots.append(encode_pos(nrr, nrc))
            
            # Capture check 2: any robot at player's position after robot move?
            captured2 = False
            for nrp in new_robots:
                if nrp == new_player_pos:
                    captured2 = True
                    break
            if captured2:
                continue
            
            new_state = (new_player_pos,) + tuple(new_robots)
            if new_state not in visited:
                visited.add(new_state)
                queue.append((new_state, new_turn))
    
    print(-1)

solve()

この解説は claude4.6opus-thinking によって生成されました。