概要

\(N \times N\) グリッド上で、開始マス \(S\) から終了マス \(T\) へ移動する途中に、指定された \(M(\le 15)\) 個のマスをすべて（順不同で）通過するときの最小移動回数を求めます。

考察

• ロボットは上下左右に1マスずつ動けるので、2点間の最短距離は「障害物なしのグリッド最短距離」＝マンハッタン距離になります。
  つまり、座標を \((r,c)\) とすると距離は \(|r_1-r_2|+|c_1-c_2|\) です。
• 盤面サイズ \(N\) は最大 \(10^5\) で、マス総数は \(N^2\) と巨大です。よって「グリッド上で BFS して最短経路を求める」ような方法は不可能です（状態数が大きすぎて TLE/メモリ超過）。
• しかし、必ず訪れる必要があるのは \(M\) 個の棚マスだけで、\(M\le 15\) と小さいのが重要です。
  経路全体の最適化は「\(S \to (棚を全部巡回) \to T\)」の巡回順序の最適化に帰着できます。
• 素朴に棚の訪問順を全探索すると \(M!\) 通りで、例えば \(M=15\) だと \(15!\approx 1.3\times 10^{12}\) で到底間に合いません。
• そこで「部分集合 DP（bit DP）」で、棚集合の訪問状況をビットマスクで管理して最短を求めます（巡回セールスマン問題の典型解法）。

アルゴリズム

1. マス番号を座標に変換
   マス番号 \(k(1\le k\le N^2)\) は左上から行優先で付いているので、

   • \(k-1\) を \(N\) で割った商が行 \(r\)、余りが列 \(c\)
     つまり \((r,c)=\text{divmod}(k-1, N)\) で求まります（0-index座標）。

2. 必要な点同士の距離を前計算
   訪問点は \(S\)、棚 \(P_1..P_M\)、\(T\) ですが、DPに使うのは以下の距離だけです。

   • \(dS[i] =\) 距離\((S, P_i)\)
   • \(d[i][j] =\) 距離\((P_i, P_j)\)
   • \(dT[i] =\) 距離\((P_i, T)\)
     いずれもマンハッタン距離で \(O(1)\) で求まります。

3. bit DP（部分集合DP）

   • 状態：\(dp[mask][i]\)
     =「棚集合 \(mask\)（ビットが立っている棚を訪問済み）をすべて訪問し、最後に棚 \(i\) にいるときの最小移動回数」
   • 初期化：棚 \(i\) を最初に訪れる場合
     \(dp[1<<i][i] = dS[i]\)
   • 遷移：\(mask\) の状態で最後が \(i\) のとき、未訪問の棚 \(j\) へ行く
     $\(dp[mask\cup\{j\}][j] = \min\Big(dp[mask\cup\{j\}][j],\ dp[mask][i] + d[i][j]\Big)\)$
   • 答え：全棚訪問後に \(T\) へ
     $\(\min_i \big(dp[full][i] + dT[i]\big)\)\( ここで \)full = (1<)-1$。

4. \(M=0\) の特別ケース
   棚がないなら単に距離\((S,T)\)（マンハッタン距離）を出力します。

（具体例）棚が3個なら \(mask\) は \(0\)〜\(7\)。例えば \(mask=101_2\) は「棚0と棚2を訪問済み」を意味し、そこから未訪問の棚1へ遷移して \(111_2\) にします。

計算量

• 時間計算量:
  距離前計算 \(O(M^2)\)、DPは状態数 \(2^M \times M\) に対して遷移が最大 \(M\) なので
  \(O(2^M \cdot M^2)\)
  （\(M\le 15\) なら十分高速です）
• 空間計算量:
  DPテーブルが \(2^M \times M\)
  \(O(2^M \cdot M)\)

実装のポイント

• 座標変換は必ず \(k-1\) に注意：番号が1始まりなので \((k-1)\) を使って divmod します。
• INF を大きく取る：DPの初期値として十分大きい値（例：\(10^{30}\)）を使います。
• 未訪問集合の列挙：rem = ((1<<M)-1) ^ mask で未訪問ビットを取り、lb = j & -j で最下位ビットを取り出すと高速に回せます。
• \(N\) が大きくても問題ない：実際に扱うのは \(S,T,P_i\) の座標だけで、グリッド全体を保持・探索しない設計になっています。

ソースコード

import sys

def coord(k, N):
    k -= 1
    return divmod(k, N)  # (r, c)

def manhattan(a, b):
    return abs(a[0] - b[0]) + abs(a[1] - b[1])

def main():
    data = sys.stdin.buffer.read().split()
    it = iter(data)

    N = int(next(it))
    M = int(next(it))
    S = int(next(it))
    T = int(next(it))

    if M == 0:
        s = coord(S, N)
        t = coord(T, N)
        print(manhattan(s, t))
        return

    P = [int(next(it)) for _ in range(M)]

    s = coord(S, N)
    t = coord(T, N)
    pts = [coord(x, N) for x in P]

    dS = [manhattan(s, pts[i]) for i in range(M)]
    dT = [manhattan(pts[i], t) for i in range(M)]
    d = [[0] * M for _ in range(M)]
    for i in range(M):
        for j in range(M):
            d[i][j] = manhattan(pts[i], pts[j])

    INF = 10**30
    size = 1 << M
    dp = [[INF] * M for _ in range(size)]
    for i in range(M):
        dp[1 << i][i] = dS[i]

    for mask in range(size):
        row = dp[mask]
        for i in range(M):
            cur = row[i]
            if cur >= INF:
                continue
            rem = ((size - 1) ^ mask)
            j = rem
            while j:
                lb = j & -j
                nj = (lb.bit_length() - 1)
                nmask = mask | lb
                val = cur + d[i][nj]
                if val < dp[nmask][nj]:
                    dp[nmask][nj] = val
                j -= lb

    full = size - 1
    ans = min(dp[full][i] + dT[i] for i in range(M))
    print(ans)

if __name__ == "__main__":
    main()

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