概要

各島を頂点、距離が \(D\) 以下で直接移動できる関係を辺とみなしたグラフ上で、島 \(S\) から島 \(T\) までの最短手数（最小移動回数）を求める問題です。

考察

• 「一度の移動で行ける島」は、現在地からユークリッド距離が \(D\) 以下の島全てです。
  つまり、島同士の到達可能性で作られる 無向グラフ を考えると、「移動回数の最小値」は 辺の本数が最小の経路長に対応します。
• 各移動は常に「1 回」なので、辺の重みは全て同じ（重み 1）です。このとき最短手数は BFS（幅優先探索）で求められます（Dijkstra は不要）。
• 素朴に「全ての島ペアについて距離を計算して辺を張り、隣接リストを作る」方法も \(O(N^2)\) で可能ですが、辺が多いとメモリ的に重くなりがちです（最悪ほぼ完全グラフ）。
  • そこで本コードでは 隣接リストを作らず、BFS で頂点を取り出すたびに「未訪問の島を全走査して、距離 \(D\) 以内なら訪問する」という形で、辺探索をその場で行います。
• 距離判定で \(\sqrt{\cdot}\) を使うと遅く、誤差も気になるので、
  $\((X_i-X_j)^2 + (Y_i-Y_j)^2 \le D^2\)$
  のように 2 乗のまま比較します。

アルゴリズム

1. 入力を読み込み、\(S, T\) を 0-index に直す。
2. \(D2 = D^2\) を用意する。
3. 配列 dist を用意し、dist[v] = -1 を未訪問、dist[S] = 0 とする。
4. キューに \(S\) を入れて BFS を行う。
   • キューから島 \(i\) を取り出す。
   • まだ未訪問の全ての島 \(j\) について、
     • \(dx = X_i - X_j, \ dy = Y_i - Y_j\)
     • \(dx^2 + dy^2 \le D2\) なら「1 回で移動可能」なので dist[j] = dist[i] + 1 としてキューへ入れる。
   • もし \(j = T\) に到達したら、その時点の距離を出力して終了（BFS なので最短が確定）。
5. BFS が終わっても dist[T] = -1 なら到達不能として -1 を出力する（到達できていればその値が答え）。

計算量

• 時間計算量: \(O(N^2)\)
  （各島を取り出したときに全島を走査するため。\(N \le 1500\) なので最大でも約 225 万回程度の距離計算で収まる。）
• 空間計算量: \(O(N)\)
  （座標配列、距離配列、キューのみ。隣接リストを持たない。）

実装のポイント

• 平方根を使わずに \(dx^2 + dy^2 \le D^2\) で判定する（高速・安全）。

• dist[j] != -1（訪問済み）なら距離計算自体をスキップして無駄を減らす。

• BFS 中に目的地 \(T\) に到達したら 即座に出力して終了できる（それが最短手数）。

  ソースコード

import sys
from collections import deque

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N, D, S, T = data[0], data[1], data[2] - 1, data[3] - 1
    coords = data[4:]
    X = coords[0::2]
    Y = coords[1::2]

    D2 = D * D
    dist = [-1] * N
    dist[S] = 0
    q = deque([S])

    while q:
        i = q.popleft()
        xi, yi = X[i], Y[i]
        nd = dist[i] + 1
        for j in range(N):
            if dist[j] != -1:
                continue
            dx = xi - X[j]
            dy = yi - Y[j]
            if dx * dx + dy * dy <= D2:
                dist[j] = nd
                if j == T:
                    print(nd)
                    return
                q.append(j)

    print(dist[T])

if __name__ == "__main__":
    main()

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