You are provided with a city map represented as a $\backslash (7\backslash$times $7\backslash )$ grid. Due to road maintenance after heavy rains, several roads are blocked, and your task is to navigate from your office to home. The goal is to find the shortest, safest route, avoiding blocked paths and restricted zones such as parks and buildings.

Constraints:

$-$ Restricted areas $($no movement allowed$)$: Roadblocks, buildings and parks

$-$ Allowed Movements: Horizontal or vertical only $($no diagonal movement$).$

Expected Output:

$-$ Optimal path from Office to Home.

$-$ Number of steps taken along the path.

$-$ Time and space complexity of algorithms.

Use the following algorithms to find the optimal path.

$-$ Iterative Deepening A$*$ Algorithm

$-$ Hill Climbing algorithms

Evaluations will be based on the following.

$1.$ Explain the PEAS and Task environment of the agent

$2.$ Define the heuristic and or fitness function for the given algorithms and the given problem. $[2$ Mark$]$

$3.$ Use appropriate data structures and implement search algorithms $($informed and local search$).$ The starting point is to be obtained from the user as input. $[3+3=6$ Mark$]4.$ Find and print space and time complexity using code in your implementation. $[2$ Mark$]$