概要

\(N\) 個の島を頂点、距離 \(D\) 以内の島同士を辺とみなしたグラフにおいて、スタートの島 \(S\) からゴールの島 \(T\) までの最短経路（最小移動回数）を求める問題です。

考察

グラフ問題への言い換え

この問題は、各島を「頂点」、移動可能な島のペアを「辺」と考えれば、典型的な単一始点最短経路問題に帰着できます。 - 頂点数 \(N\)：最大 1500 - 辺の条件：2島間のユークリッド距離 \(\sqrt{(X_i - X_j)^2 + (Y_i - Y_j)^2} \leq D\)

距離計算の工夫

ユークリッド距離の計算には平方根（sqrt）が含まれますが、浮動小数点数を使うと誤差が生じる可能性があります。 不等式の両辺を2乗することで、整数のみの計算で判定が可能です。 $\((X_i - X_j)^2 + (Y_i - Y_j)^2 \leq D^2\)$ この工夫により、誤差を気にせず正確に判定を行うことができます。

最短経路のアルゴリズム

重みのないグラフ（すべての辺の長さが 1）における最短経路を求めるため、幅優先探索 (BFS) を使用するのが最適です。 \(N = 1500\) であるため、あらかじめすべての島同士の距離を計算して隣接リストを作る手法（\(O(N^2)\)）でも間に合いますが、今回の実装では探索中に「まだ訪れていない島」のみを効率的にチェックすることで、無駄な計算を省いています。

アルゴリズム

1. 初期化:
   • 各島への最短距離を保持する配列 dist を \(-1\)（未訪問）で初期化し、出発地点 dist[S] = 0 とします。
   • 未訪問の島のリスト unvisited を作成します。
   • 探索用のキュー queue に出発地点 \(S\) を入れます。
2. 幅優先探索 (BFS):
   • キューから島 \(u\) を取り出します。
   • unvisited リストにある各島 \(v\) について、島 \(u\) からの距離が \(D\) 以下かどうかを判定します。
   • 距離が \(D\) 以下であれば：
     • dist[v] = dist[u] + 1 と更新します。
     • 島 \(v\) が目的地 \(T\) であれば、その時点の dist[v] を出力して終了します。
     • 島 \(v\) をキューに追加し、unvisited から除外します。
3. 終了処理:
   • キューが空になっても \(T\) に到達できなければ、\(-1\) を出力します。

計算量

• 時間計算量: \(O(N^2)\)
  • 各島は最大1回キューに入ります。
  • 各ステップで unvisited リストを走査します。1つの島のペアに対して距離判定が行われるのは高々1回であるため、全体で \(O(N^2)\) となります。\(N=1500\) のとき \(N^2 = 2.25 \times 10^6\) であり、制限時間内に十分収まります。
• 空間計算量: \(O(N)\)
  • 座標データ、距離配列、キュー、未訪問リストの保持に \(O(N)\) のメモリを使用します。

実装のポイント

• 高速な入出力: \(N\) が比較的大きいため、sys.stdin.read().split() などを用いて一括で入力を読み込むと実行時間を短縮できます。

• 0-indexed への変換: 問題文では島番号が 1 から \(N\) ですが、プログラム上では 0 から \(N-1\) として扱うと配列のインデックス操作がスムーズになります。

• 未訪問リストの管理: すでに訪れた島を再度チェックしないように unvisited リストを更新していくことで、探索の効率を高めています。

  ソースコード

import sys
from collections import deque

def solve():
    # すべての入力を一括で読み込みます
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 基本パラメータのパース
    # N: 島の数, D: 一度に移動できる最大距離, S: 出発する島, T: 目的の島
    N = int(input_data[0])
    D = int(input_data[1])
    S = int(input_data[2]) - 1  # 0-indexedに変換
    T = int(input_data[3]) - 1  # 0-indexedに変換
    
    # 各島の座標を読み込みます
    X = [0] * N
    Y = [0] * N
    for i in range(N):
        X[i] = int(input_data[4 + 2*i])
        Y[i] = int(input_data[5 + 2*i])
        
    # ユークリッド距離の比較を高速化するため、距離の2乗を計算しておきます
    D2 = D * D
    
    # 幅優先探索 (BFS) を用いて最短移動回数を求めます
    # dist[i] は島 S から島 i までの最小移動回数を保持します
    dist = [-1] * N
    dist[S] = 0
    queue = deque([S])
    
    # まだ訪れていない島のリストを保持します
    # これにより、探索済みの島を何度もチェックするのを避けます
    unvisited = [i for i in range(N) if i != S]
    
    while queue:
        u = queue.popleft()
        ux, uy = X[u], Y[u]
        
        # 今回のステップで訪問できなかった島を保持するための新しいリスト
        next_unvisited = []
        for v in unvisited:
            dx = ux - X[v]
            dy = uy - Y[v]
            # 浮動小数点の誤差を避けるため、2乗の状態で比較を行います
            if dx * dx + dy * dy <= D2:
                dist[v] = dist[u] + 1
                # 目的地に到達した場合、即座に結果を出力して終了します
                if v == T:
                    print(dist[v])
                    return
                queue.append(v)
            else:
                # 到達できなかった島は次回の探索候補として残します
                next_unvisited.append(v)
        
        # 未訪問リストを更新
        unvisited = next_unvisited
        
    # キューが空になっても目的地 T に到達できなかった場合
    print("-1")

if __name__ == '__main__':
    solve()

この解説は gemini-3-flash-thinking によって生成されました。