 # 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 = 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"
``````