概要

ロボットが指定された複数のマスを経由しながら、スタートからゴールまで最短距離で移動する問題。経由地の訪問順序は自由だが、全ての経由地を少なくとも1回通る必要がある。

考察

この問題は、単純にBFSなどで全経路を探索しようとすると、グリッドサイズ \(N\) が最大 \(10^5\) となるため、現実的ではありません（計算量的に無理）。また、経由地の数 \(M\) は最大15と小さいことに注目します。

ロボットは上下左右にしか移動できないので、2点間の最短距離はマンハッタン距離で求めることができます。したがって、重要な地点（スタート、ゴール、経由地）同士の距離を前計算しておくことで、経由地の訪問順序を最適化する問題に帰着できます。

これは典型的な「巡回セールスマン問題（TSP）」の変形であり、bit DP を用いることで効率的に解くことができます。bit DP を使うことで、どの経由地を訪れたかという情報をビットで管理しながら最小コストを更新していきます。

アルゴリズム

1. 各マスのIDからグリッド上の座標 \((r, c)\) に変換する関数 id_to_xy を定義。
2. 任意の2点間のマンハッタン距離を計算する関数 manhattan_distance を定義。
3. スタート \(S\)、ゴール \(T\)、および \(M\) 個の経由地 \(P_1, ..., P_M\) をノードとして持つグラフを考える。
4. これらのノード同士の距離を前計算し、距離テーブル dist_table を作成。
5. bit DP を用いて、訪問済みノード集合（bitmask）と現在位置を状態とした最小コストを更新：
   • dp[mask][i] := ビットマスク mask で表されるノード集合を訪問し、現在位置がノード i であるときの最小コスト。
6. 初期状態は dp[1][0] = 0（スタート地点のみ訪問済み）。
7. bit DP の遷移では、次にどの未訪問ノードに行くかを全探索し、最小コストを更新していく。
8. 最終的に、すべての経由地を訪問した上でゴールに到達する最小コストを求める。

計算量

• 時間計算量: \(O(M^2 + M \cdot 2^M \cdot M) = O(M^2 \cdot 2^M)\)
• 空間計算量: \(O(M^2 + M \cdot 2^M)\)

※ \(M \leq 15\) なので、bit DP による指数時間でも十分間に合う。

実装のポイント

• グリッド上のマス番号から \((r, c)\) 座標への変換を正確に行うこと。
• マンハッタン距離の計算は誤らないように注意。
• bit DP において、遷移時に mask に含まれていないノードだけを選んで次の状態に進む。
• 最終的な答えは、「すべての経由地を訪問済み」かつ「最後にゴールに向かう」場合の最小コスト。

ソースコード

import sys
from collections import deque

def id_to_xy(id, N):
    id -= 1
    return (id // N, id % N)

def manhattan_distance(id1, id2, N):
    r1, c1 = id_to_xy(id1, N)
    r2, c2 = id_to_xy(id2, N)
    return abs(r1 - r2) + abs(c1 - c2)

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    M = int(data[1])
    S = int(data[2])
    T = int(data[3])
    P = list(map(int, data[4:4+M]))
    
    # 頂点リスト：S, P1,...,PM, T
    nodes = [S] + P + [T]
    L = len(nodes)
    
    # 距離テーブルを前計算
    dist_table = [[0]*L for _ in range(L)]
    for i in range(L):
        for j in range(i+1, L):
            d = manhattan_distance(nodes[i], nodes[j], N)
            dist_table[i][j] = d
            dist_table[j][i] = d
    
    # dp[mask][i] := maskで表される頂点集合を訪問し、現在位置がnodes[i]である最小コスト
    INF = float('inf')
    dp = [[INF]*L for _ in range(1 << L)]
    
    # 初期位置はS (nodes[0])
    dp[1][0] = 0
    
    # bit DP
    for mask in range(1 << L):
        for u in range(L):
            if not (mask & (1 << u)):
                continue
            if dp[mask][u] == INF:
                continue
            current_cost = dp[mask][u]
            for v in range(L):
                if mask & (1 << v):
                    continue
                new_mask = mask | (1 << v)
                new_cost = current_cost + dist_table[u][v]
                if new_cost < dp[new_mask][v]:
                    dp[new_mask][v] = new_cost
    
    # 答え：すべての経由地（P）を通ってT（nodes[-1]）に到達する最小コスト
    # T以外の経由地は nodes[1] ～ nodes[M]
    target_mask = (1 << (M+1)) - 1  # SとP1～PM
    ans = INF
    for i in range(1, L):  # 最後はT (nodes[-1] = nodes[M+1])
        if dp[target_mask][i] != INF:
            ans = min(ans, dp[target_mask][i] + dist_table[i][L-1])
    
    print(dp[(1 << L) - 1][L-1])

if __name__ == "__main__":
    main()

---

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