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 shortest, and safest path. Use the following algorithms to find the safest path. Interpret if the path obtained is the shortest with

justification.

a$.$ Depth First Search

Note:$-$

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. Evaluations will be based on the following.

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

$2.$ Use Depth First Search and implement the algorithms in PYTHON. Interpret the results in terms of

the algorithm working, performance & shortest path if obtained relevant to the given problem.

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

$4.$ Include code in you implementation to calculate the space complexity and time complexity.