Python. BFS Solution


#1

We first create a visited 2D array where we mark the coordinates which are invalid. For (x, y), we cannot visit if (1) we have already visited previously, or (2) coordinate lies within the radius of the circle.

To determine whether the coordinate lies within the circle, we use distance formula:

For coordinate (x, y), it lies within the circle with origin (x0, y0) and radius of r iff 

(x - x0)^2 + (y - y0)^2 <= radius^2.

Once we have initialized our visited array, we can use either DFS or BFS to try to explore valid path to the target (x, y) from (0, 0).

class Solution:
    # @param A : integer
    # @param B : integer
    # @param C : integer
    # @param D : integer
    # @param E : list of integers
    # @param F : list of integers
    # @return a strings
    def solve(self, m, n, N, radius, circle1, circle2):
        
        visited = [[False] * (n + 1) for _ in range(m + 1)]
        
        for x in range(m + 1):
            for y in range(n + 1):
                for x0, y0 in zip(circle1, circle2):
                    if (x - x0) ** 2 + (y - y0) ** 2 <= radius ** 2:
                        visited[x][y] = True
        
        queue = [(0,0)]
        visited[0][0] = True
        while queue:
            x, y = queue.pop()
            if (x, y) == (m, n):
                return "YES"
            for nx, ny in [(x+dx,y+dy) for dx in (-1,0,1) for dy in (-1,0,1)]:
                if nx == x and ny == y:
                    continue
                if 0 <= nx < m + 1 and 0 <= ny < n + 1 and not visited[nx][ny]:
                    visited[nx][ny] = True
                    queue.append((nx,ny))
        
        return "NO"