Problem statement

Given below is the picture of a city as a grid. Due to heavy rains and water clogging, some paths are blocked for traffic. You are in your office and have to reach home quickly because of further rain and flood warnings. You have a GPS agent to help you find the shortest, quickest and safest route through the available paths avoiding the blockades so that you reach home safely. You are provided with the map of the city with the current situation marked. Use the following algorithms to find the safest path. Interpret if the path obtained is the shortest with justification.

a$.$ Breadth First Search and

b$.$ Recursive Best First Search

Note $1$:

No diagonal movements allowed. You cannot pass through other buildings. $5$ points to be added when your path passes adjacent $($next to and not diagonally$)$ to other buildings. $3$ points to be detected when your path passes adjacent to road blocks. The path which passes through minimum number of squares and maximum points is the shortest and safest path.

Explain the PEAS $($Performance measure, Environment, Actuator, Sensor.$)$ for your agent.

Use Breadth First Search and Recursive Best First Search and implement the algorithms in PYTHON. Compare to interpret the results in terms of the algorithm working, performance & shortest path if obtained relevant to the given problem.

Print the path, the total points for the path and the number of squares in the path.

Include code in your implementation to calculate the space complexity and time complexity and print the same.

In the solution provided earlier the code ia working in such a way that path is going through the blocked $($cross marked$)$ cells. The solution we need is that it should go through blocked path and builings and shouldnt travel diagonally too