Overview

This is a problem where we model each island as a vertex and the relationship of being able to directly travel between islands within distance \(D\) as edges in a graph, then find the shortest number of moves (minimum number of trips) from island \(S\) to island \(T\).

Analysis

• The “islands reachable in one move” are all islands within Euclidean distance \(D\) from the current location.
  In other words, if we consider the undirected graph formed by the reachability between islands, the “minimum number of moves” corresponds to the path length with the minimum number of edges.
• Since each move always counts as “1 step,” all edge weights are the same (weight 1). In this case, the shortest number of moves can be found using BFS (Breadth-First Search) (Dijkstra is unnecessary).
• A straightforward approach of “computing distances for all pairs of islands, adding edges, and building an adjacency list” is possible in \(O(N^2)\), but when there are many edges, it can become memory-intensive (worst case is nearly a complete graph).
  • Therefore, in this code, instead of building an adjacency list, each time a vertex is dequeued during BFS, we “scan all unvisited islands and visit those within distance \(D\),” performing edge exploration on the fly.
• Using \(\sqrt{\cdot}\) for distance comparison is slow and introduces precision concerns, so we compare using squared values:
  $\((X_i-X_j)^2 + (Y_i-Y_j)^2 \le D^2\)$

Algorithm

1. Read the input and convert \(S, T\) to 0-indexed.
2. Prepare \(D2 = D^2\).
3. Prepare an array dist, setting dist[v] = -1 as unvisited and dist[S] = 0.
4. Enqueue \(S\) and perform BFS.
   • Dequeue island \(i\).
   • For all still-unvisited islands \(j\):
     • \(dx = X_i - X_j, \ dy = Y_i - Y_j\)
     • If \(dx^2 + dy^2 \le D2\), the island is “reachable in one move,” so set dist[j] = dist[i] + 1 and enqueue it.
   • If \(j = T\) is reached, output the distance at that point and terminate (since BFS guarantees it is the shortest).
5. If BFS finishes and dist[T] = -1, output -1 as the destination is unreachable (otherwise, the stored value is the answer).

Complexity

• Time complexity: \(O(N^2)\)
  (Because we scan all islands each time an island is dequeued. With \(N \le 1500\), this amounts to at most about 2.25 million distance calculations.)
• Space complexity: \(O(N)\)
  (Only the coordinate arrays, distance array, and queue. No adjacency list is stored.)

Implementation Notes

• Use \(dx^2 + dy^2 \le D^2\) for comparison without using square roots (fast and safe).

• If dist[j] != -1 (already visited), skip the distance calculation entirely to reduce unnecessary work.

• If the destination \(T\) is reached during BFS, output immediately and terminate (this is guaranteed to be the shortest number of moves).

  Source Code

import sys
from collections import deque

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N, D, S, T = data[0], data[1], data[2] - 1, data[3] - 1
    coords = data[4:]
    X = coords[0::2]
    Y = coords[1::2]

    D2 = D * D
    dist = [-1] * N
    dist[S] = 0
    q = deque([S])

    while q:
        i = q.popleft()
        xi, yi = X[i], Y[i]
        nd = dist[i] + 1
        for j in range(N):
            if dist[j] != -1:
                continue
            dx = xi - X[j]
            dy = yi - Y[j]
            if dx * dx + dy * dy <= D2:
                dist[j] = nd
                if j == T:
                    print(nd)
                    return
                q.append(j)

    print(dist[T])

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.