Shortest Path on a Huge Map with A*
The map is a huge grid (0 = free, 1 = obstacle) and many routes have to be computed on it, so exploring every cell within reach of the start is too slow. Movement is one cell per step, up, down, left or right.
Implement A* search: return the length of the shortest path from src to dst (each [row, col]), or -1 when there is none, while expanding cells in order of distance-so-far plus a heuristic estimate of the distance left.
grid = [[0, 1, 0],
[0, 1, 0],
[0, 0, 0]]
astarGrid(grid, [0, 0], [0, 2]) -> 6The tests check the answer, which must match BFS exactly — a heuristic that overestimates will fail some of them.
Hints
Hint 1
A* is Dijkstra with a priority of g + h: g is the steps taken so far, h estimates the steps left. With 4-directional unit steps, the Manhattan distance to dst never overestimates.
Hint 2
An admissible heuristic (never overestimating) keeps A* optimal. Keep the best g seen per cell and skip stale heap entries.