Problem Statement $1$: You are tasked with implementing the $A^{**}$ algorithm to find the shortest path on a grid$-$based map between two points. The map consists of a rectangular grid where each cell can be passable or impassable. Your task is to find the shortest path from the start to the target cell while avoiding impassable cells. You can implement the $A^{**}$ algorithm in Python and test it on the map provided.

Start Node $=$ S$,$ Target Node $=$ T$,$ Intermediate Nodes $=1,2,3,4,5$

Adjacency Cost Matrix $=$

S $12345$ T

S $0100000$

$11010000$

$20101010$

$30010100$

$40001001$

$50010001$

T $0000110$

Heuristic $=$ Manhattan Distance $($minimum distance to target node T$)$