概要

スタート地点から複数の経由地点を全て訪れてゴールに到達する最短経路を求める問題で、巡回セールスマン問題（TSP）の一種です。ビットマスクDPを用いて効率的に解きます。

考察

重要な気づき

1. グリッド上の最短距離はマンハッタン距離: 障害物がないグリッド上で2点間を移動する最短距離は、マンハッタン距離（\(|r_1 - r_2| + |c_1 - c_2|\)）で計算できます。BFSなどを使う必要はありません。

2. 経由地点の訪問順序が問題: \(M\) 個の経由地点をどの順番で訪れるかによって総移動距離が変わります。最適な順序を見つける必要があります。

素朴なアプローチの問題点

全ての経由地点の訪問順序を試す方法では、\(M!\) 通りの順列を調べることになります。\(M = 15\) の場合、\(15! \approx 1.3 \times 10^{12}\) となり、時間内に処理できません。

解決策

ビットマスクDPを使います。「どの経由地点を訪問済みか」をビットマスクで管理し、同じ状態は再計算しないようにします。これにより計算量を \(O(M! )\) から \(O(2^M \times M^2)\) に削減できます。

アルゴリズム

1. 座標変換とマンハッタン距離の計算

マス番号 \(k\)（1-indexed）から座標への変換：

• 行: \((k-1) \div N\)
• 列: \((k-1) \mod N\)

2. 距離行列の構築

スタート \(S\)、ゴール \(T\)、経由地点 \(P_1, \ldots, P_M\) の全 \((M+2)\) 点間のマンハッタン距離を事前計算します。

3. ビットマスクDP

状態を以下のように定義します：

• \(dp[\text{mask}][i]\) = スタートから始めて、\(\text{mask}\) で表される経由地点の集合を訪問し、最後に経由地点 \(i\) にいるときの最小移動距離

初期状態: スタートから各経由地点 \(i\) への直接移動
\(dp[2^i][i] = \text{dist}(S, P_i)\)

遷移: 経由地点 \(\text{last}\) から未訪問の経由地点 \(\text{next}\) へ移動
\(dp[\text{mask} | 2^{\text{next}}][\text{next}] = \min(dp[\text{mask} | 2^{\text{next}}][\text{next}], dp[\text{mask}][\text{last}] + \text{dist}(P_{\text{last}}, P_{\text{next}}))\)

4. 答えの計算

全経由地点を訪問後（\(\text{mask} = 2^M - 1\)）、各最終地点からゴールへの距離を加えた最小値が答えです：
\(\text{ans} = \min_{i=0}^{M-1} \left( dp[2^M - 1][i] + \text{dist}(P_i, T) \right)\)

計算量

• 時間計算量: \(O(M^2 + 2^M \times M^2)\)
  • 距離行列の構築: \(O((M+2)^2) = O(M^2)\)
  • ビットマスクDP: 状態数 \(O(2^M \times M)\)、各状態からの遷移 \(O(M)\)
• 空間計算量: \(O(2^M \times M)\)
  • DPテーブルのサイズ

\(M \leq 15\) なので、\(2^{15} \times 15^2 \approx 7 \times 10^6\) 程度で十分高速に動作します。

実装のポイント

• インデックス管理: points 配列で \(S\) をインデックス0、\(T\) をインデックス1、経由地点を2以降に配置。DPでは経由地点を0〜\(M-1\)で管理するため、points 配列へのアクセス時は +2 が必要。
• \(M = 0\) の場合: 経由地点がなければ、単純に \(S\) から \(T\) へのマンハッタン距離が答え。
• ビットマスクの操作: mask & (1 << i) で \(i\) 番目が訪問済みか確認、mask | (1 << i) で \(i\) 番目を訪問済みに更新。

ソースコード

import sys
from itertools import permutations

def solve():
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    S = int(input_data[idx]); idx += 1
    T = int(input_data[idx]); idx += 1
    
    P = []
    for i in range(M):
        P.append(int(input_data[idx])); idx += 1
    
    # マス番号から座標(row, col)に変換 (0-indexed)
    def to_coord(num):
        num -= 1  # 0-indexed
        row = num // N
        col = num % N
        return (row, col)
    
    # マンハッタン距離を計算
    def manhattan(p1, p2):
        r1, c1 = to_coord(p1)
        r2, c2 = to_coord(p2)
        return abs(r1 - r2) + abs(c1 - c2)
    
    # 全ての重要な点（S, T, P[0..M-1]）
    # S: index 0
    # T: index 1
    # P[i]: index i+2
    points = [S, T] + P
    num_points = len(points)
    
    # 距離行列を計算
    dist = [[0] * num_points for _ in range(num_points)]
    for i in range(num_points):
        for j in range(num_points):
            dist[i][j] = manhattan(points[i], points[j])
    
    if M == 0:
        # 経由地点がない場合、SからTへ直接
        print(dist[0][1])
        return
    
    # ビットマスクDPで巡回セールスマン問題を解く
    # dp[mask][i] = Sから始まり、maskで表される経由地点を訪れ、最後に経由地点iにいるときの最小距離
    # 経由地点のインデックスは 0 から M-1 (points配列では 2 から M+1)
    
    INF = float('inf')
    dp = [[INF] * M for _ in range(1 << M)]
    
    # 初期状態: Sから各経由地点への距離
    for i in range(M):
        dp[1 << i][i] = dist[0][i + 2]  # Sから経由地点iへ
    
    # DP遷移
    for mask in range(1, 1 << M):
        for last in range(M):
            if not (mask & (1 << last)):
                continue
            if dp[mask][last] == INF:
                continue
            # 次の経由地点へ
            for next_p in range(M):
                if mask & (1 << next_p):
                    continue
                new_mask = mask | (1 << next_p)
                new_dist = dp[mask][last] + dist[last + 2][next_p + 2]
                if new_dist < dp[new_mask][next_p]:
                    dp[new_mask][next_p] = new_dist
    
    # 全ての経由地点を訪れた後、Tへ移動
    full_mask = (1 << M) - 1
    ans = INF
    for last in range(M):
        if dp[full_mask][last] < INF:
            total = dp[full_mask][last] + dist[last + 2][1]  # 最後の経由地点からTへ
            ans = min(ans, total)
    
    print(ans)

solve()

---

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