For the $2$D occupancy

grid shown to the right

$(4-$connected cells, unit

cost to move$),$ find the

shortest path from cell S

to cell G by A$*$ using the

Manhattan distance $($L$1$

norm, taxicab distance$)$

as the heuristic.