class Stan:
    def __init__(self, x, y, kierunek):
        self.x = x
        self.y = y
        self.kierunek = kierunek


class Wezel:
    def __init__(self, stan):
        self.stan = stan


def poprzednik(wezel):
    # gora -> prawo -> dol -> lewo          | obrot w prawo
    # gora -> lewo -> dol -> prawo          | obrot w lewo
    # 0 gora 1 prawo 2 dol 3 lewo
    y = wezel.stan.x
    x = wezel.stan.y
    obrot_w_prawo = Stan(x, y, (wezel.stan.kierunek + 1) % 4)
    obrot_w_lewo = Stan(x, y, (wezel.stan.kierunek - 1) % 4)

    if wezel.stan.kierunek == 0:
        y -= 1
    elif wezel.stan.kierunek == 1:
        x += 1
    elif wezel.stan.kierunek == 2:
        y += 1
    elif wezel.stan.kierunek == 3:
        x -= 1

    wezly = [obrot_w_prawo, obrot_w_lewo]
    ruch_w_przod = Stan(x, y, wezel.stan.kierunek)

    # sprawdzenie czy nie wyjdzie poza plansze
    if 0 <= x <= 916 and 0 <= y <= 916:
        wezly.append(ruch_w_przod)

    return wezly


def wyszukiwanie_bfs(stan_poczatkowy, stan_docelowy):
    pierwszy_wezel = Wezel(stan_poczatkowy)
    fringe = [pierwszy_wezel]

    odwiedzone = list()

    while fringe:
        # kolejka
        wezel = fringe.pop(0)

        if stan_docelowy.x == wezel.stan.x and stan_docelowy.y == wezel.stan.y:
            return odwiedzone

        odwiedzone.append(wezel)

        for stan in poprzednik(wezel):
            if wezel not in fringe and stan not in odwiedzone:
                nowy_wezel = Wezel(stan)
                fringe.append(nowy_wezel)