Python3 Very Clean Code! Help required to resolve TLE!


Code Description:

  1. slove(self, rect_x, rect_y, num_circles, radius, circ_x, circ_y)
    rect_x => maximum x co-ordinate of rectangle (int)
    rect_y => maximum y co-ordinate of rectangle (int)
    num_circles => number of circles (int)
    radius => radius of circles (int)
    circ_x => x co-ordinates of centers of all circles (list:int)
    circ_y => y co-ordinates of centers of all circles (list:int)
    return True/False if path/not path

  2. is_point_inside_circle(self, point, circles_params)
    point: x co-ordinate and y co-ordinate of the point (tuple)
    circles_params: list containing circ_x, circ_y, radius
    returns True if point inside circle else False

  3. bfs(queue, end, visited, circles_params)
    queue (deque)
    end: end co-ordinates (tuple)
    visited: (set)
    returns True if we reached end else False

  4. get_legal_moves(position, end)
    position: tuple of current position
    returns list containing all legal moves possible from current position in the grid

  5. distance_between_points(p, q)
    p,q: (tuples) points on grid
    returns Eucledian distance between them


from collections import deque
from math import sqrt, floor, ceil
class Solution:
    def distance_between_points(self, p, q):
        return math.sqrt(sum((px - qx) ** 2.0 for px, qx in zip(p, q)))
    def is_point_inside_circle(self, point, circles_params):
        circ_x, circ_y, radius = circles_params
        row, col = point
        for cur_x, cur_y in zip(circ_x, circ_y):
            if self.distance_between_points((row, col), (cur_x, cur_y)) < radius: return True
        return False
    def get_legal_moves(self, position, end):
        dirs = [[1, 0], [0, 1], [-1, 0], [0, -1], [1, 1], [-1, -1], [-1, 1], [1, -1]]
        ans = []
        for [row, col] in dirs:
            next_x, next_y = position[0] + row, position[1] + col
            if 0 <= next_x <= end[0] and 0 <= next_y <= end[1]: ans.append((next_x, next_y))
        return ans
    def bfs(self, queue, end, visited, circles_params):
        while queue:
            cur = queue.pop()
            if cur == end: return True
            legal_moves = self.get_legal_moves(cur, end)
            for (row, col) in legal_moves:
                if (row, col) not in visited and not self.is_point_inside_circle((row, col), circles_params) : queue.appendleft((row, col))
        return False
    def solve(self, rect_x, rect_y, num_circles, radius, circ_x, circ_y):
        visited = set()
        circles_params = [circ_x, circ_y, radius]
        if radius == 0: return "YES"
        if self.is_point_inside_circle((0, 0), circles_params) or self.is_point_inside_circle((rect_x, rect_y), circles_params): return "NO"
        queue = deque([(0, 0)])
        if self.bfs(queue, (rect_x, rect_y), visited, circles_params): 
            return "YES"
            return "NO"