Overview

Given the coordinates of each island, this is a graph search problem where you can move to any island within a maximum movement distance \(D\), and you need to find the minimum number of moves from island \(S\) to island \(T\).

Analysis

This problem involves constructing a graph where islands are vertices and pairs of reachable islands are edges, then finding the shortest path using Breadth-First Search (BFS). An important point is that instead of using the actual Euclidean distance, we use the squared distance for comparison, which avoids square root calculations and prevents floating-point errors. Since \(N\) is at most 1500, an \(O(N^2)\) approach that computes distances between all pairs of vertices to construct the graph is feasible.

Algorithm

1. Read input data and store island coordinates in an array
2. Compute the square of the distance threshold \(D\) (i.e., \(D^2\))
3. For all pairs of islands \((i, j)\), compute the squared distance
   • If the squared distance is less than or equal to \(D^2\), add a bidirectional edge to the undirected graph
4. Use Breadth-First Search (BFS) to find the shortest path from island \(S\) to island \(T\)
   • If reachable, output the number of moves
   • If unreachable, output \(-1\)

Complexity

• Time complexity: \(O(N^2)\)
  • \(O(N^2)\) for graph construction
  • \(O(N + E)\) for BFS (where \(E\) is the number of edges)
• Space complexity: \(O(N^2)\)
  • Up to \(O(N^2)\) for the adjacency list representation of the graph

Implementation Notes

• When comparing distances, avoid square root calculations by comparing squared distances, improving computational efficiency and avoiding precision issues

• Since processing is 0-indexed, subtract 1 from the input values of \(S\) and \(T\)

• Represent the graph as an adjacency list and search efficiently with BFS

• Use a visited management array to record the minimum number of moves to each island

  Source Code

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

This editorial was generated by deepseekv3.