Q$3.$ Consider a simple grid world where the goal is to find the shortest path from the starting point $\backslash ((\backslash$mathrm$\{$S$\})\backslash )$ to the goal $\backslash ((\backslash$mathrm$\{$G$\})\backslash ).$ The grid is represented as follows:

S: Start G: Goal $.$: Empty cell $\backslash$#: Obstacle

A Search:$*$

$-$ Apply the A$*$ search algorithm to find the shortest path from the start $($S$)$ to the goal $($G$)$ on the provided grid.

$-$ Use the Manhattan distance heuristic for estimating the cost from each cell to the goal.

$-$ Write down the sequence of cells visited and the final path found by the $\backslash ($ A$^\{*\}\backslash )$ algorithm.