概要

\(N\) 個の島があり、それぞれの島は二次元平面上の座標に配置されている。島から島への移動は、ユークリッド距離が \(D\) 以下の場合に可能である。島 \(S\) から島 \(T\) への最小移動回数を求めよ。

考察

この問題は、島を頂点、移動可能な島の組を辺としたグラフ上の最短経路問題として捉えることができます。

まず、どの島からどの島に移動可能かを判定する必要があります。これは、各島のペアに対してユークリッド距離を計算し、それが \(D\) 以下であれば辺を張ることで実現できます。ただし、愚直に全ペアの距離を計算すると、\(O(N^2)\) かかりますが、制約 \(N \leq 1500\) なので、十分間に合います。

次に、グラフが構築できれば、あとは「最短経路」つまり「最小の辺数」で島 \(S\) から島 \(T\) に到達する方法を求めるだけです。これは典型的な 幅優先探索 (BFS) によって効率的に求めることができます。

素朴なDFSなどでは最短でない経路を見つける可能性があるため、最短経路を保証するにはBFSが適しています。

また、距離の比較では平方根を計算する必要がないため、距離の二乗を比較することで高速化できます。つまり、

\[ \sqrt{(x_i - x_j)^2 + (y_i - y_j)^2} \leq D \iff (x_i - x_j)^2 + (y_i - y_j)^2 \leq D^2 \]

とすることで、浮動小数点演算を避けても正しい結果を得られます。

アルゴリズム

1. 各島の座標を読み込む。
2. 各島のペアに対して、距離の二乗を計算し、\(D^2\) 以下であれば無向辺を張る。
3. 島 \(S\) から始まるBFSを行い、各島への最短距離を求める。
4. 島 \(T\) への最短距離を出力する（到達不能なら \(-1\)）。

計算量

• 時間計算量: \(O(N^2 + N + M)\) （ここで \(M\) は辺の数。最悪ケースで \(O(N^2)\)）
• 空間計算量: \(O(N + M)\)

実装のポイント

• 距離の比較は平方根を使わず、二乗のまま比較することで高速かつ誤差フリー。
• BFSを行う際、訪問済みフラグではなく距離配列を用いて dist[v] == -1 で未訪問を管理すると簡潔。
• 入力を高速に読み込むために sys.stdin.read を使用している。
• 頂点番号は 0-indexed に変換して処理すると実装が楽（入力は 1-indexed）。

## ソースコード

```python
from collections import deque
import math

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx]); idx += 1
    D = int(data[idx]); idx += 1
    S = int(data[idx]); idx += 1
    T = int(data[idx]); idx += 1
    S -= 1
    T -= 1
    
    X = [0]*N
    Y = [0]*N
    for i in range(N):
        X[i] = int(data[idx]); idx += 1
        Y[i] = int(data[idx]); idx += 1
        
    # グラフ構築
    G = [[] for _ in range(N)]
    D2 = D*D
    for i in range(N):
        for j in range(i+1, N):
            dx = X[i] - X[j]
            dy = Y[i] - Y[j]
            dist_sq = dx*dx + dy*dy
            if dist_sq <= D2:
                G[i].append(j)
                G[j].append(i)
                
    # BFS
    dist = [-1]*N
    que = deque()
    dist[S] = 0
    que.append(S)
    
    while que:
        v = que.popleft()
        d = dist[v]
        for w in G[v]:
            if dist[w] == -1:
                dist[w] = d + 1
                que.append(w)
                
    print(dist[T])

if __name__ == "__main__":
    main()

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