AtCoder Beginner Contest 304 C - Virusの解答
・説明:dequeを使って実装する。dequeに0人目(1人目)を入れて、感染した人をif d>=math.sqrt(dx*dx+dy*dy):の条件分岐でdequeに入れていく。 これをwhileでdequeが空になるまでやる。また感染しているかどうかはflagで管理する(例えばflag[i]=1だとi番目の人は感染している)。
・実装:
import math from collections import deque n,d=map(int,input().split()) xy=[list(map(int,input().split())) for _ in range(n)] #print(xy) que=deque() que.append(0) #0(1人目)から flag=[0 for _ in range(n)] #感染した人はflag=1 flag[0]=1 #print(flag) while len(que)!=0: p=que.popleft() for j in range(n): #print(p,j) if j!=p: dx=xy[p][0]-xy[j][0] dy=xy[p][1]-xy[j][1] if d>=math.sqrt(dx*dx+dy*dy): #感染者の近くにいたら if flag[j]==0: #flag[j]=1はすでに感染しているので0のとき。これないと無限ループする flag[j]=1 que.append(j) for i in range(n): if flag[i]==1: print("Yes") else: print("No")