[伯俊]9205 Python-ビールを飲みながら歩く

ビールを飲みながら歩く
入力:
第1行は、試験例の個数tを与える.(t ≤ 50)
各テストボックスの最初の行には、ビールを売っているコンビニの数nが与えられています.(0 ≤ n ≤ 100).
次のn+2行は、上根家、コンビニ、PentaPortrock Festival座標を与えます.各座標は2つの整数xとyからなる.(両方ともm,−32768≦x,y≦32767)
松島は長方形の町です.2つの座標間の距離は、x座標の差+y座標の差である.(マンハッタン通り)
出力:
各テストボックスについて、尚根と友人たちが幸せに祭りに行くことができれば、「happy」、中間ビールが切れて移動できない場合は「sad」を出力します.
入力例:
2
2
0 0
1000 0
1000 1000
2000 1000
2
0 0
1000 0
2000 1000
2000 2000
出力例:
happy
sad

from collections import deque
import sys

input = sys.stdin.readline

def bfs():
  queue = deque()
  queue.append(start)
  visited = [False]*n    #편의점의 수만큼 방문 여부를 체크하

  while queue:
    x,y = queue.popleft()
    if abs(x-end[0])+ abs(y-end[1]) <= 1000:    #목적지와 현재 위치의 거리가 1000이하 (20*50)라면,
      return True    
    for i in range(n):    #편의점의 개수만큼 반복
      if visited[i] == False:    #i번째 편의점을 방문하지 않았다면,
        
        nx,ny =data[i]    #편의점의 좌표를 nx,ny에 저장
        if abs(x-nx)+abs(y-ny)<=1000:    #현재위치와, 편의점의 위치의 거리가 1000이하라면,
          visited[i] = True    #방문 처리를 하고,
          queue.append([nx,ny])    #큐에 편의점의 위치를 추가.
  return False    #중간에 True가 리턴되지 않는경우, 거리가 1000을 초과하는 경우, False 리턴


t = int(input())    #테스트 케이스의 수

for _ in range(t):
  n = int(input())    #편의점의 수
  data = []
  start = list(map(int,input().split()))    #출발할 집의 좌표
  for _ in range(n):
    data.append(list(map(int,input().split())))    #편의점의 좌표를 수만큼 입력
  end = list(map(int,input().split()))    #목적지의 좌표
  result = bfs()    #bfs함수의 반환값을 result변수에 저장
  if result:    #result가 True이면,
    print('happy')
  else:    #result가 True가 아니라면,
    print('sad')