A* Pathfinding Heuristic

Implement A* search with Manhattan distance to find the shortest path in a grid.

search heuristic shortest-path priority-queue

You are given a 2D grid represented as a list of lists of integers, where 0 indicates an open cell and 1 indicates a blocked cell. You may move in four directions (up, down, left, right) only, and cannot move onto a blocked cell. The start and goal are given as (row, col) tuples. Implement the function `astar_path(grid, start, goal)` that returns the length of the shortest path from start to goal using A* with the Manhattan distance heuristic. If no path exists, return -1. Assume the start and goal are within bounds and open; if start equals goal, the path length is 0. The input grid is non-empty and rectangular.

Constraints

Grid dimensions: at most 200x200 (up to 40,000 cells). The input grid is always rectangular. The start and goal coordinates are always valid and open. The function should be efficient enough to handle the maximum grid size in a reasonable time (A* with Manhattan heuristic is acceptable).

Example

>>> grid = [
...     [0, 0, 1],
...     [1, 0, 0],
...     [0, 0, 0]
... ]
>>> astar_path(grid, (0,0), (2,2))
4
>>> astar_path(grid, (0,0), (0,2))
-1
>>> astar_path(grid, (0,0), (0,0))
0

25 points ~30 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Use a priority queue (heapq) to always expand the node with the smallest f = g + h.

Manhattan distance from current cell to goal is |r - goal_r| + |c - goal_c|.

Keep track of visited nodes with their best g-score to avoid revisiting worse paths.

If the goal is popped from the queue, return its g-score immediately; otherwise return -1 if the queue empties.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.