def a_star(graph, start, goal, h):

        open_set = []
        heapq.heappush(open_set, (h(start), 0, start, [start]))  # (f = g+h, g, node, path)

        visited = set()

        while open_set:
            f, g, node, path = heapq.heappop(open_set)

            if node == goal:
                return path, g

            if node in visited:
                continue
            visited.add(node)

            for neighbor, cost in graph[node]:
                if neighbor not in visited:
                    g_new = g + cost
                    f_new = g_new + h(neighbor)
                    heapq.heappush(open_set, (f_new, g_new, neighbor, path + [neighbor]))

        return None, float('inf')  # no path found

    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:

        import heapq
        from typing import List

        
        # A* Algorithm (Heuristic Guided Shortest Path)
        # ---------------------------------------------------
        # Goal:
        # Find shortest path from (0,0) → (n-1,n-1)
        #
        # Core Idea:
        # - Similar to Dijkstra, but guided using heuristic.
        # - Priority = g(n) + h(n)
        #
        # g(n) = distance travelled so far
        # h(n) = estimated distance to goal (Chebyshev distance)

        n = len(grid)

        # ---------------------------------------------------
        # Step 1: Early Pruning
        # ---------------------------------------------------
        if grid[0][0] == 1 or grid[n-1][n-1] == 1:
            return -1

        # 8 directions
        directions = [
            (1,0), (-1,0), (0,1), (0,-1),
            (1,1), (1,-1), (-1,1), (-1,-1)
        ]

        # ---------------------------------------------------
        # Heuristic Function (Chebyshev Distance)
        # ---------------------------------------------------
        def heuristic(r, c):
            return max(abs(n-1-r), abs(n-1-c))

        # ---------------------------------------------------
        # MinHeap:
        # (f = g+h, g, row, col)
        # ---------------------------------------------------
        heap = [(1 + heuristic(0,0), 1, 0, 0)]

        visited = set()

        # ---------------------------------------------------
        # A* Traversal
        # ---------------------------------------------------
        while heap:

            f, dist, r, c = heapq.heappop(heap)

            if (r, c) in visited:
                continue
            visited.add((r, c))

            # Goal reached
            if r == n-1 and c == n-1:
                return dist

            # Explore neighbors
            for dr, dc in directions:
                nr, nc = r + dr, c + dc

                # valid + clear cell
                if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0:
                    if (nr, nc) not in visited:

                        g = dist + 1
                        h = heuristic(nr, nc)

                        heapq.heappush(heap, (g + h, g, nr, nc))

        return -1

    def slidingPuzzle(self, board):
        start = "".join(str(x) for row in board for x in row)
        target = "123450"

        # index -> neighbors where 0 can move
        neighbors = {
            0: [1, 3],
            1: [0, 2, 4],
            2: [1, 5],
            3: [0, 4],
            4: [1, 3, 5],
            5: [2, 4]
        }

        # goal positions for Manhattan distance
        goal_pos = {
            '1': (0, 0),
            '2': (0, 1),
            '3': (0, 2),
            '4': (1, 0),
            '5': (1, 1)
        }

        def heuristic(state):
            """Manhattan distance"""
            dist = 0
            for i, ch in enumerate(state):
                if ch == '0':
                    continue
                r, c = divmod(i, 3)
                gr, gc = goal_pos[ch]
                dist += abs(r - gr) + abs(c - gc)
            return dist

        # (f, g, state)
        heap = []
        heappush(heap, (heuristic(start), 0, start))

        visited = set()

        while heap:
            f, g, state = heappop(heap)

            if state == target:
                return g

            if state in visited:
                continue
            visited.add(state)

            zero_idx = state.index('0')

            for nxt in neighbors[zero_idx]:
                new_state = list(state)
                new_state[zero_idx], new_state[nxt] = (
                    new_state[nxt],
                    new_state[zero_idx],
                )
                new_state = "".join(new_state)

                if new_state not in visited:
                    new_g = g + 1
                    new_f = new_g + heuristic(new_state)
                    heappush(heap, (new_f, new_g, new_state))

        return -1