概要

高橋君（プレイヤー）と最大 \(2\) 体の警備ロボットが同じ迷宮内で同時進行する状況を、状態遷移の最短探索（BFS）としてモデル化し、最小ターンで出口に到達できるかを判定します。

考察

重要な気づき

• この問題は「高橋君が最適に動く」とあるので、最短ターン数を求める典型問題に見えますが、ロボットが動くため単純な最短路ではありません。
• しかしロボットの動きは
  • 壁を避けつつ（通路のみ）、
  • 高橋君の“そのターンの移動後の位置”だけを見て、
  • ルール通りに決定的に決まります。

つまり、あるターンで「高橋君の位置」と「各ロボットの位置」が分かれば、次のターンの状態は（高橋君の選択を除けば）一意に定まります。

素朴なアプローチが難しい理由

• 「高橋君の位置だけ」で BFS すると WA になります。ロボット位置が違えば次の危険度が変わるため、同じマスでも状況が別物だからです。
• 逆に「ターン数を大きくしてシミュレーションで最適行動を探す」ような方法は、循環（同じ状況に戻る）が起こり得るため、どこで打ち切ればよいか分からず不安定です。

解決方針

• 状態を（高橋君位置, ロボット位置(最大2体)）として BFSします。
• BFS なら「最初に出口に到達したターン」が最小ターンだと保証されます。
• 状態数は \(N,M\le 8\) なので最大マス数は \(64\)、ロボットも最大 \(2\) 体で、状態数は高々 \(64^3=262144\) 程度に収まります。

アルゴリズム

状態定義

• 1 マスを ID \(v \in [0, NM)\) に変換して扱います。
• 状態は
  • \(K=0\): \((t)\)
  • \(K=1\): \((t, r_1)\)
  • \(K=2\): \((t, r_1, r_2)\)
    ここで \(t\) は高橋君の位置、\(r_i\) はロボットの位置です。

遷移（1ターン分）

BFS の 1 ステップが「1ターン」に対応します。現在状態から次状態を次の順で作ります。

1. 高橋君の行動候補を列挙
   上下左右＋とどまる（最大5通り）で、通路のみを許可。

2. 捕獲判定1（高橋君移動後）
   高橋君の移動先 to がロボット位置と一致したら、その手は失敗（遷移しない）。

3. 脱出判定（高橋君移動後）
   to == G なら、その時点で脱出成功。
   BFS なので、ここでのターン数 depth+1 が最小です。

4. ロボット移動（同時）
   各ロボットについて、候補（上下左右＋とどまる）のうち

   • 高橋君の位置 to へのマンハッタン距離が最小
   • 同値なら優先順位「上→下→左→右→とどまる」

で 1 つに決定し、その移動先を nr とします。

1. 捕獲判定2（ロボット移動後）
   ロボット移動後に nr == to があれば失敗（遷移しない）。

2. 未訪問ならキューに追加
   同じ状態に再訪しても意味がない（以後も同じ展開を繰り返す可能性が高い）ので、visited で管理します。

状態の圧縮（実装上）

\(NM \le 64\) なので 1 位置を 6bit で表せます。
コードでは - 高橋君: 下位 6bit - ロボ1: 次の 6bit - ロボ2: 次の 6bit
として 1 つの整数に詰め、visited を集合で管理しています。

計算量

状態数は高々 \(64^{1+K}\)、各状態からの分岐は高橋君の最大5手、ロボット移動計算も各ロボット最大5候補なので定数です。

• 時間計算量: \(O(64^{1+K})\)（厳密には \(O(5 \cdot 5K \cdot 64^{1+K})\) だが定数）
• 空間計算量: \(O(64^{1+K})\)（訪問済み状態とキュー）

実装のポイント

• 捕獲判定の順番が重要です。問題文通りに
  「高橋君移動後に捕獲→脱出判定→ロボット移動→捕獲」
  を厳密に守らないと WA になります。

• ロボットの候補は「上・下・左・右・とどまる」の優先順位が必要なので、候補リストをその順で作っておき、距離が同じなら先に出てきたものが選ばれるようにします（コードでは rob_cands[pos] をその順で保持）。

• BFS 中に to == G を見つけた瞬間に答えを出してよいのは、BFS がターン数（深さ）の昇順で探索するためです。

  ソースコード

import sys
from collections import deque

def main():
    input = sys.stdin.readline
    N, M, K = map(int, input().split())
    Sr, Sc = map(int, input().split())
    Gr, Gc = map(int, input().split())
    Sr -= 1; Sc -= 1
    Gr -= 1; Gc -= 1

    robots_rc = []
    for _ in range(K):
        pr, qc = map(int, input().split())
        robots_rc.append((pr - 1, qc - 1))

    grid = [input().strip() for _ in range(N)]
    cells = N * M

    def cid(r, c): return r * M + c

    passable = [False] * cells
    for r in range(N):
        row = grid[r]
        for c in range(M):
            if row[c] == '.':
                passable[cid(r, c)] = True

    r_of = [i // M for i in range(cells)]
    c_of = [i % M for i in range(cells)]

    # Takahashi moves (U, D, L, R, Stay) within passable cells
    dirs = [(-1, 0), (1, 0), (0, -1), (0, 1), (0, 0)]
    taka_moves = [[] for _ in range(cells)]
    for v in range(cells):
        if not passable[v]:
            continue
        r, c = r_of[v], c_of[v]
        lst = []
        for dr, dc in dirs:
            nr, nc = r + dr, c + dc
            if 0 <= nr < N and 0 <= nc < M:
                nv = cid(nr, nc)
                if passable[nv]:
                    lst.append(nv)
        taka_moves[v] = lst

    # Robot candidate moves in priority order (U, D, L, R, Stay)
    rob_cands = [[] for _ in range(cells)]
    for v in range(cells):
        if not passable[v]:
            continue
        r, c = r_of[v], c_of[v]
        cand = []
        for dr, dc in dirs:
            nr, nc = r + dr, c + dc
            if 0 <= nr < N and 0 <= nc < M:
                nv = cid(nr, nc)
                if passable[nv]:
                    cand.append(nv)
        rob_cands[v] = cand

    def robot_move(pos, target):
        tr, tc = r_of[target], c_of[target]
        best = None
        bestd = 10**9
        for nv in rob_cands[pos]:  # already in priority order
            d = abs(r_of[nv] - tr) + abs(c_of[nv] - tc)
            if d < bestd:
                bestd = d
                best = nv
        return best

    S = cid(Sr, Sc)
    G = cid(Gr, Gc)
    robot_ids = [cid(r, c) for (r, c) in robots_rc]

    # Pack state into int using 6 bits per position (cells<=64)
    MASK = 63
    if K == 0:
        init = S
    elif K == 1:
        init = S | (robot_ids[0] << 6)
    else:
        init = S | (robot_ids[0] << 6) | (robot_ids[1] << 12)

    q = deque([(init, 0)])
    visited = {init}

    while q:
        state, depth = q.popleft()

        if K == 0:
            t = state
            r1 = r2 = None
        elif K == 1:
            t = state & MASK
            r1 = state >> 6
            r2 = None
        else:
            t = state & MASK
            r1 = (state >> 6) & MASK
            r2 = state >> 12

        for to in taka_moves[t]:
            # Capture check 1
            if K == 1:
                if to == r1:
                    continue
            elif K == 2:
                if to == r1 or to == r2:
                    continue

            turn = depth + 1
            # Escape check
            if to == G:
                print(turn)
                return

            # Robots move + capture check 2
            if K == 0:
                ns = to
            elif K == 1:
                nr1 = robot_move(r1, to)
                if nr1 == to:
                    continue
                ns = to | (nr1 << 6)
            else:
                nr1 = robot_move(r1, to)
                nr2 = robot_move(r2, to)
                if nr1 == to or nr2 == to:
                    continue
                ns = to | (nr1 << 6) | (nr2 << 12)

            if ns not in visited:
                visited.add(ns)
                q.append((ns, depth + 1))

    print(-1)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。