We have a rectangular grid of points where one corner is (0,0) and the other corner is (𝑊,𝐻), where &#11

[answerhappygod]

We have a rectangular grid of points where one corner is (0,0)
and the other corner is (𝑊,𝐻), where
𝑊,𝐻 represent the width and height of the grid,
respectively. From each point (𝑥,𝑦), we can move
along one of the cardinal directions to (𝑥′,𝑦′) ∈
{(𝑥+1,𝑦) ,(𝑥−1,𝑦)
,(𝑥,𝑦+1), (𝑥,𝑦−1)}, as long as
0≤𝑥′≤𝑊 and 0≤𝑦′≤𝐻 (i.e, we are
not allowed to move out of the grid).
Furthermore, we specify a set of 𝑘 circles 𝐶 =
{(𝑥1,𝑦1,𝑟1),…,(𝑥𝑘,𝑦𝑘,𝑟𝑘)}
where each circle has center
(𝑥𝑖,𝑦𝑖) and radius
𝑟𝑖.
The goal is to find a path from (0,0) to (𝑊,𝐻)
while avoiding any point on the surface of or inside the circles in
𝐶. If such a path is found, your algorithm should return
the path as a list of grid points. If not, your algorithm should
return the empty list.
Example 1
Consider 𝑊 =𝐻 = 3 and two circles 𝐶 =
{(1,2,1),(2,2,0.5)}.

We Have A Rectangular Grid Of Points Where One Corner Is 0 0 And The Other Corner Is W H Where W H Represent The Wi 1 (14.68 KiB) Viewed 53 times

The red lines show a path from (0,0) to (3,3). Your algorithm
may return a list [(0,0), (1,0), (2,0), (3, 0), (3,1), (3,2), (3,3)
] (there is another path in this case and any of them may be
returned.
Example 2
Consider 𝑊=𝐻=3and two circles
𝐶={(1,2,1),(2,2,1)}.

We Have A Rectangular Grid Of Points Where One Corner Is 0 0 And The Other Corner Is W H Where W H Represent The Wi 2 (14.89 KiB) Viewed 53 times

There are no paths in this case (in particular (3,2) lies on the
orange circle though this is not 100% clear from the picture). Your
algorithm should return the empty list. Note, coding language used
is python
from math import sqrt
# You may use this function to test if a point lies inside given
circle.
def ptInCircle(x,y, circles_list):
for (xc,yc,rc) in circles_list:
d = sqrt ( (x-xc)**2 +
(y-yc)**2)
if d <= rc:

return True
return False
def findPath(width, height, forbidden_circles_list):
# width is a positive number
# height is a positive number
# forbidden_circles_list is a list of triples
[(x1, y1, r1),..., (xk, yk, rk)]
assert width >= 1
assert height >= 1
assert all(x <= width and x >=0 and y
<= height and y >= 0 and r > 0 for (x,y,r) in
forbidden_circles_list)
# your code here
To check for correctness
def checkPath(width, height, circles, path):
assert path[0] == (0,0), 'Path must begin at
(0,0)'
assert path[-1] == (width, height), f'Path must
end at {(width, height)}'
(cur_x, cur_y) = path[0]
for (new_x, new_y) in path[1:]:
dx = new_x - cur_x
dy = new_y - cur_y
assert (dx,dy) in
[(1,0),(-1,0), (0,1),(0,-1)]
assert 0 <= new_x and
new_x <= width
assert 0 <= new_y and
new_y <= height
assert not
ptInCircle(new_x, new_y, circles)
cur_x, cur_y = new_x,
new_y
return
print('-- Test 1 -- ')
circles = [(2,2,0.5), (1,2,1)]
p = findPath(3, 3, circles)
print(p)
checkPath(3, 3, circles, p)
print('-- Test 2 -- ')
circles1 = [(2,2,1), (1,2,1)]
p1 = findPath(3, 3, circles1)
print(p1)
assert p1 == [], 'Answer does not match with ours'
print('-- Test 3 -- ')
p2 = findPath(5,5, circles1)
print(p2)
checkPath(5, 5, circles1, p2)
print('-- Test 4 --')
circles3 = [(1,2,0.5), (2,2,1), (3,3,1),(4,3,1)]
p3 = findPath(5, 5, circles3)
print(p3)
checkPath(5, 5, circles3, p3)
print('-- Test 5 --')
circles5 = [ (4,1, 1), (4,4,1),(2,6,1)]
p5 = findPath(6,6,circles5)
print(p5)
assert p5 == []
print('All tests passed: 15 points!')
3 2 1 0 0 1 1 0.5 2 3

3 2 1 О О 1 1 2 3