概要

二次元平面上に配置された \(N\) 個の島の間を、ユークリッド距離 \(D\) 以下の島へ繰り返し移動して、島 \(S\) から島 \(T\) への最小移動回数を求める最短経路問題です。

考察

重要な気づき

• 2つの島の間に「辺」があるかどうかは、ユークリッド距離が \(D\) 以下かどうかで決まります。つまり、島をノード、距離 \(D\) 以下のペアを辺としたグラフ上での最短経路問題に帰着できます。
• 各辺の重み（コスト）は「1回の移動」で等しいため、重み無しグラフの最短経路問題です。重み無しグラフの最短経路は BFS（幅優先探索） で求められます。

素朴なアプローチとその妥当性

• 全ペアの距離を事前に計算して隣接リストを作ると、\(O(N^2)\) の前処理が必要です。\(N \leq 1500\) なので \(N^2 = 2{,}250{,}000\) 程度であり、十分高速に処理できます。
• もし \(N\) が \(10^5\) 以上であれば \(O(N^2)\) は厳しくなりますが、本問では \(N \leq 1500\) なので問題ありません。

ユークリッド距離の比較の工夫

• ユークリッド距離 \(\sqrt{(X_u - X_v)^2 + (Y_u - Y_v)^2} \leq D\) の判定は、両辺を2乗して \((X_u - X_v)^2 + (Y_u - Y_v)^2 \leq D^2\) とすることで、平方根の計算を避け、整数演算のみで正確に判定できます。

アルゴリズム

1. 入力を読み込み、各島の座標を保存する。
2. \(D^2\) を事前に計算しておく。
3. 島 \(S\) を始点として BFS を行う。
   • キューから島 \(u\) を取り出すたびに、全島 \(v\)（\(0 \leq v < N\)）に対して：
     • まだ訪問していない（dist[v] == -1）かつ距離条件 \((X_u - X_v)^2 + (Y_u - Y_v)^2 \leq D^2\) を満たすなら、\(v\) を訪問済みにしてキューに追加。
   • 島 \(T\) に到達したら、その時点の移動回数を出力。
4. BFS が終了しても島 \(T\) に到達できなかった場合は \(-1\) を出力。

具体例

例えば、3つの島が \((0,0)\), \((3,0)\), \((7,0)\) にあり、\(D=4\), \(S=1\), \(T=3\) の場合： - 島1→島2：距離 \(3 \leq 4\) なので移動可能 - 島2→島3：距離 \(4 \leq 4\) なので移動可能 - 島1→島3：距離 \(7 > 4\) なので直接は移動不可

よって、島1→島2→島3 と2回の移動で到達でき、答えは \(2\) です。

計算量

• 時間計算量: \(O(N^2)\)
  • BFS の各ステップで、キューから取り出したノードに対して全 \(N\) ノードを走査します。各ノードがキューに入るのは高々1回なので、全体で \(O(N \times N) = O(N^2)\) です。
• 空間計算量: \(O(N)\)
  • 座標配列、距離配列、BFS のキューにそれぞれ \(O(N)\) を使用します。隣接リストを明示的に構築しないため、\(O(N^2)\) のメモリは不要です。

実装のポイント

• 隣接リストを事前構築しない: BFS の探索中にその場で距離判定を行うことで、メモリを節約しつつ実装もシンプルにできます。

• 距離の2乗で比較: 浮動小数点演算による誤差を完全に回避するため、\(D^2\) と距離の2乗を整数で比較します。座標や \(D\) が最大 \(10^9\) なので、2乗すると最大 \(4 \times 10^{18}\) 程度になりますが、Python は多倍長整数を扱えるためオーバーフローの心配はありません。

• 早期終了: 島 \(T\) に到達した時点で即座に結果を出力して終了することで、不要な探索を省略します。

  ソースコード

import sys
from collections import deque

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    D = int(input_data[idx]); idx += 1
    S = int(input_data[idx]) - 1; idx += 1
    T = int(input_data[idx]) - 1; idx += 1
    
    X = [0] * N
    Y = [0] * N
    for i in range(N):
        X[i] = int(input_data[idx]); idx += 1
        Y[i] = int(input_data[idx]); idx += 1
    
    D2 = D * D
    
    # BFS with distance check on the fly (N<=1500, so O(N^2) is fine)
    dist = [-1] * N
    dist[S] = 0
    queue = deque([S])
    
    while queue:
        u = queue.popleft()
        if u == T:
            print(dist[T])
            return
        for v in range(N):
            if dist[v] == -1:
                dx = X[u] - X[v]
                dy = Y[u] - Y[v]
                if dx * dx + dy * dy <= D2:
                    dist[v] = dist[u] + 1
                    queue.append(v)
    
    print(-1)

main()

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