from queue import PriorityQueue

def is_valid(state):
    M_left, C_left, boat = state

    M_right = 3 - M_left
    C_right = 3 - C_left

    if M_left > 0 and M_left < C_left:
        return False

    if M_right > 0 and M_right < C_right:
        return False

    return True

def heuristic(state):
    return state[0] + state[1]

def best_first_search():
    start = (3, 3, 1)
    goal = (0, 0, 0)

    pq = PriorityQueue()
    pq.put((heuristic(start), start, []))

    visited = set()

    while not pq.empty():
        _, state, path = pq.get()

        if state in visited:
            continue

        visited.add(state)
        path = path + [state]

        if state == goal:
            return path

        M, C, boat = state

        moves = [
            (1, 0),
            (2, 0),
            (0, 1),
            (0, 2),
            (1, 1)
        ]

        for m, c in moves:

            if boat == 1:
                new_state = (M - m, C - c, 0)
            else:
                new_state = (M + m, C + c, 1)

            if 0 <= new_state[0] <= 3 and 0 <= new_state[1] <= 3:

                if is_valid(new_state):
                    pq.put((heuristic(new_state), new_state, path))

result = best_first_search()

print("Solution Path:")

for step in result:
    print(step)