AtCoder Beginner Contest 304 C - Virusの解答

atcoder.jp

・説明: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")