Overview

There are \(N\) islands, each placed at coordinates on a two-dimensional plane. Movement from one island to another is possible if the Euclidean distance between them is at most \(D\). Find the minimum number of moves to get from island \(S\) to island \(T\).

Analysis

This problem can be interpreted as a shortest path problem on a graph where islands are vertices and pairs of islands that can be traveled between are edges.

First, we need to determine which islands can be reached from which. This is done by computing the Euclidean distance for each pair of islands and adding an edge if the distance is at most \(D\). Although naively computing distances for all pairs takes \(O(N^2)\), given the constraint \(N \leq 1500\), this is fast enough.

Once the graph is constructed, all that remains is to find the “shortest path,” i.e., the path with the “minimum number of edges,” from island \(S\) to island \(T\). This can be efficiently solved using a classic Breadth-First Search (BFS).

A naive DFS might find a non-shortest path, so BFS is the appropriate choice to guarantee the shortest path.

Additionally, when comparing distances, there is no need to compute square roots — we can compare squared distances instead for faster computation. That is,

\[ \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 \]

This allows us to obtain correct results while avoiding floating-point arithmetic.

Algorithm

1. Read the coordinates of each island.
2. For each pair of islands, compute the squared distance. If it is at most \(D^2\), add an undirected edge.
3. Perform BFS starting from island \(S\) to find the shortest distance to each island.
4. Output the shortest distance to island \(T\) (or \(-1\) if it is unreachable).

Complexity

• Time complexity: \(O(N^2 + N + M)\) (where \(M\) is the number of edges; worst case \(O(N^2)\))
• Space complexity: \(O(N + M)\)

Implementation Notes

• Compare distances using squared values instead of square roots for speed and to avoid floating-point errors.

• When performing BFS, using a distance array and checking dist[v] == -1 for unvisited nodes is cleaner than using a separate visited flag.

• sys.stdin.read is used for fast input reading.

• Converting vertex indices to 0-indexed simplifies the implementation (input is 1-indexed).

  Source Code

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()

This editorial was generated by qwen3-coder-480b.