概要

各島の座標が与えられ、最大移動距離\(D\)以下の島へ移動できるとき、島\(S\)から島\(T\)までの最小移動回数を求めるグラフ探索問題です。

考察

島を頂点、移動可能な島のペアを辺とするグラフを構築し、幅優先探索(BFS)で最短経路を求める問題です。重要な点は、ユークリッド距離の計算に実際の距離ではなく距離の二乗を用いることで、平方根計算を避け浮動小数点誤差を防げることです。\(N\)が最大1500と小さいため、全頂点間の距離を計算してグラフを構築する\(O(N^2)\)のアプローチが可能です。

アルゴリズム

1. 入力データを読み込み、島の座標を配列に格納
2. 距離の閾値\(D\)の二乗を計算（\(D^2\)）
3. すべての島のペア\((i, j)\)について、距離の二乗を計算
   • 距離の二乗が\(D^2\)以下の場合、無向グラフに双方向の辺を追加
4. 幅優先探索(BFS)を使用して、島\(S\)から島\(T\)への最短経路を探索
   • 到達可能な場合は移動回数を出力
   • 到達不能な場合は\(-1\)を出力

計算量

• 時間計算量: \(O(N^2)\)
  • グラフ構築に\(O(N^2)\)
  • BFSに\(O(N + E)\)（\(E\)は辺の数）
• 空間計算量: \(O(N^2)\)
  • グラフの隣接リスト表現に最大\(O(N^2)\)

実装のポイント

• 距離比較時には平方根計算を避け、距離の二乗同士を比較することで計算効率向上と精度問題を回避

• 0-indexedで処理するため、入力された\(S\)と\(T\)から1を減算

• グラフを隣接リストで表現し、BFSで効率的に探索

• 訪問管理配列で各島への最小移動回数を記録

  ソースコード

import sys
from collections import deque

def main():
    data = sys.stdin.read().split()
    if not data:
        print(-1)
        return
        
    n = int(data[0])
    D = int(data[1])
    S = int(data[2]) - 1
    T = int(data[3]) - 1
    
    coords = []
    index = 4
    for i in range(n):
        x = int(data[index])
        y = int(data[index+1])
        index += 2
        coords.append((x, y))
    
    D_sq = D * D
    
    graph = [[] for _ in range(n)]
    
    for i in range(n):
        x1, y1 = coords[i]
        for j in range(i + 1, n):
            x2, y2 = coords[j]
            dx = x1 - x2
            dy = y1 - y2
            dist_sq = dx * dx + dy * dy
            if dist_sq <= D_sq:
                graph[i].append(j)
                graph[j].append(i)
    
    if S == T:
        print(0)
        return
        
    visited = [-1] * n
    queue = deque()
    queue.append(S)
    visited[S] = 0
    
    while queue:
        current = queue.popleft()
        if current == T:
            print(visited[current])
            return
            
        for neighbor in graph[current]:
            if visited[neighbor] == -1:
                visited[neighbor] = visited[current] + 1
                queue.append(neighbor)
                
    print(-1)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。