The problem goes like this:
You have a drone that can fly for a distance of D before it runs out of battery.
There are N charging stations that can fully charge up a drone.
Write a program to determine whether there is a way to fly a drone (initially fully charged) from your location to a target location via zero or more intermediate charging stations.
Each charging station is denoted by (x, y), and the Cartesian distance is taken between the points.
I tried writing a recursive code, that, however, fails on an edge case:
import math
def distance(c1, c2): # fucntion to calculate distance between two cordinates
return math.sqrt(((c2[0] - c1[0]) ** 2) + (
(c2[1] - c1[1]) ** 2)) # using sqrt function calculating distance between two cordinates
l = list(map(int, input().split())) # taking input as list using map,split function
dis = l[1]
cordinates = [] # empty list for storing cordinates as tuples
k = l[0] + 2 # for looping purpose because we have to take location and destination cordinates also
for i in range(k):
x, y = map(int, input().split())
cordinates.append((x, y))
location = cordinates[-2] # assing location as 2nd last input
del cordinates[-2] # removing from list
destination = cordinates[-1] # assining destination as last input
del cordinates[-1]
def drone(loc, des, cord): # function taking location,destination,cordinates list as parameters
if (distance(loc,
des)) <= dis: # if distance between location cordinates and destination cordinate is less than or equal to max distance of drone can travel
return 'y'
else:
if len(cord) == 0: # if cordinates list are empty
return 'n'
else:
flag = 0
for j in range(len(cord)): # finding the cordiante from the location the drone can travel
if distance(loc, cord[j]) <= dis:
loc = cord[j] # changing the location to the cordinate
flag = 1
del cord[j]
break
if flag == 0: # if flag==0 means there is no cordinate that drone can reach
return 'n'
else:
return drone(loc, des, cord) # if cordinate found calling function with new location
print(drone(location, destination, cordinates))
Test Case:
5 8
1 14
5 20
21 18
1 22
13 12
18 17
7 11
-n
+y
Can someone explain where I am going wrong, or suggest an alternate solution? I am bad at graphs