水雷阵列

import sys
from queue import PriorityQueue
import math

def is_pass(R, sorted_locs):
    q = []
    temp_y = 0
    book=[0]*len(sorted_locs)
    for i in range(len(sorted_locs)):
        if sorted_locs[i][1] <= R:
            book[i]=1
            q.append(i)
        else:
            break

    while len(q)>0:
        loc = q.pop(0)
        temp_y = max(temp_y,sorted_locs[loc][1] + R)
        if temp_y>=100.0:
            break
        for i in range(0,len(sorted_locs)):
            if book[i]==1:
                continue
            if ((sorted_locs[loc][0]-sorted_locs[i][0])**2+(sorted_locs[loc][1]-sorted_locs[i][1])**2)**0.5<=2*R:
                q.append(i)
                book[i]=1
            if sorted_locs[i][1]>sorted_locs[loc][1]+2*R:
                break
    if temp_y>=100:
        return 'N'
    return 'Y'

def counter1(R, sorted_locs,D):
    book = [0] * len(sorted_locs)
    q = PriorityQueue()
    temp_y = 0
    res_count= math.ceil(100/(2*D))
    for i in range(len(sorted_locs)):
        if sorted_locs[i][1] < R:
            q.put((0, i))
        else:
            diff= math.ceil((sorted_locs[i][1]-R)/(2*D))
            q.put((diff, i))
    while not q.empty():
        diff, loc = q.get()
        x,y= sorted_locs[loc]
        if y+R>temp_y:
            temp_y = max(temp_y,y + R)
            if temp_y<=100.0:
                res_count = min(res_count, diff + math.ceil((100 - y - R) / (2 * D)))
            else:
                res_count = min(res_count, diff)
            if temp_y >= 100.0:
                break

        if temp_y>=100.0:
            break
        book[loc]=1
        for i in range(len(sorted_locs)):
            if book[i]==1:
                continue
            if ((x - sorted_locs[i][0]) ** 2 + (
                    y - sorted_locs[i][1]) ** 2) ** 0.5 < 2 * R:
                q.put((diff,i))

            else:
                diff_new = math.ceil((((x - sorted_locs[i][0]) ** 2 + (
                            y - sorted_locs[i][1]) ** 2) ** 0.5 - 2 * R) / (2 * D))
                q.put((diff+diff_new,i))
    return res_count

for line in sys.stdin:
    inputs = line.split()
    N, R, D = int(inputs[0]), float(inputs[1]), float(inputs[2])
    locs = [(float(inputs[i]), float(inputs[i + 1])) for i in range(3, len(inputs), 2)]
    sorted_locs = sorted(locs, key=lambda x: x[1])
    res= is_pass(R,sorted_locs)
    if D==0 :
        print(res)
    else:
        if  res=='N':
            print(res)
        else:
            res= counter1(R,sorted_locs,D)
            print(res)

其实这题就是宽度优先搜索，第一问是看能否搜到对边，第二问是看搜到对面中间需要加多少，注意需要记录以前访问过的，不然会一直循环导致超时，在代码中使用book标记访问过的点。Now，show my code！