Untitled

def read_map_for_ida(filename):
    """Reads the map file and returns grid, start, and goal for IDA*."""
    with open(filename, 'r') as f:
        n, m = map(int, f.readline().split())
        grid = []
        start = None
        goal = None
        for i in range(n):
            row = f.readline().split()
            grid.append(row)
            for j in range(m):
                cell = row[j]
                if cell == "S":
                    start = (i, j)
                elif cell == "G":
                    goal = (i, j)
    return grid, start, goal

def is_inside(grid, x, y):
    n = len(grid)
    m = len(grid[0])
    return 0 <= x < n and 0 <= y < m

def get_cell_cost(grid, current_position, next_position):
    current_x, current_y = current_position
    next_x, next_y = next_position
    current_cell = grid[current_x][current_y]
    next_cell = grid[next_x][next_y]
    if next_cell == "S" or next_cell == "G":
        return 1
    if next_cell.startswith("B"):
        bridge_cost = int(next_cell[1:])
        if current_cell == next_cell:
            return 0
        else:
            return bridge_cost
    return int(next_cell)

def get_neighbors(grid, position):
    x, y = position
    moves = [
        ("UP", x - 1, y),
        ("DOWN", x + 1, y),
        ("LEFT", x, y - 1),
        ("RIGHT", x, y + 1)
    ]
    neighbors = []
    for action, new_x, new_y in moves:
        if is_inside(grid, new_x, new_y):
            new_position = (new_x, new_y)
            cost = get_cell_cost(grid, position, new_position)
            neighbors.append((action, new_position, cost))
    return neighbors

def heuristic(position, goal):
    x1, y1 = position
    x2, y2 =