A* becomes Dijkstra. A safe heuristic estimates remaining cost without exceeding it.

g is proven cost from start; h is hopeful cost to finish. The queue prioritizes their sum. The hope may guide but must not lie upward if optimality is required.

What the function promises: Return shortest four-neighbor grid steps avoiding blocked cells, or -1. Manhattan distance is admissible because each move changes it by at most one.

from heapq import heappush, heappop

def astar_grid(grid, start, goal):
    rows, cols = len(grid), len(grid[0])
    def h(cell): return abs(cell[0]-goal[0]) + abs(cell[1]-goal[1])
    distance = {start: 0}
    heap = [(h(start), 0, start)]
    while heap:
        _, spent, (r, c) = heappop(heap)
        if spent != distance[r, c]: continue
        if (r, c) == goal: return spent
        for nr, nc in ((r-1,c),(r+1,c),(r,c-1),(r,c+1)):
            if 0 <= nr < rows and 0 <= nc < cols and not grid[nr][nc]:
                candidate = spent + 1
                if candidate < distance.get((nr,nc), float("inf")):
                    distance[nr,nc] = candidate
                    heappush(heap, (candidate+h((nr,nc)), candidate, (nr,nc)))
    return -1

board = [[0,0,0],[1,1,0],[0,0,0]]
assert astar_grid(board,(0,0),(2,2)) == 4
assert astar_grid([[0,1],[1,0]],(0,0),(1,1)) == -1

Work and storage: Worst-case O((V+E) log V) with this heap implementation; a helpful heuristic often explores fewer states.

When to recognize it: A safe heuristic estimates remaining cost without exceeding it.

Check before applying it: An overestimating or inconsistent heuristic can break early-finalization assumptions; performance can still be poor.

Choose a lower-bound heuristic matching those moves; Manhattan distance may overestimate when a diagonal cheaply fixes two coordinates.