import heapq

def astar(grid, start, goal):
    rows, cols, moves = len(grid), len(grid[0]), [(-1, 0), (1, 0), (0, -1), (0, 1)]
    h = lambda a, b: abs(a[0] - b[0]) + abs(a[1] - b[1])  # Manhattan heuristic
    open_list, visited = [(0 + h(start, goal), 0, start, [])], set()

    while open_list:
        _, g, pos, path = heapq.heappop(open_list)
        if pos in visited: continue
        path, visited = path + [pos], visited | {pos}
        if pos == goal: return path
        for dx, dy in moves:
            neighbor = (pos[0] + dx, pos[1] + dy)
            if 0 <= neighbor[0] < rows and 0 <= neighbor[1] < cols and grid[neighbor[0]][neighbor[1]] == 0:
                heapq.heappush(open_list, (g + 1 + h(neighbor, goal), g + 1, neighbor, path))
    return None

# Example grid (0 = open path, 1 = obstacle)
grid = [[0, 1, 0, 0, 0],
        [0, 1, 0, 1, 0],
        [0, 0, 0, 1, 0],
        [1, 1, 1, 1, 0],
        [0, 0, 0, 0, 0]]

start, goal = (0, 0), (4, 0)
path = astar(grid, start, goal)

if path:
    for x, y in path: grid[x][y] = "*"
    for row in grid: print(" ".join(str(c) if c != "*" else "*" for c in row))
else:
    print("No path found!")