program wp09zad3;

const
    SZEROKOSC_STRONY = 595;
    WYSOKOSC_STRONY = 842;
    MARGINES_POZIOMY = 20;
    SRODEK_SZEROKOSCI = SZEROKOSC_STRONY / 2;
    SZEROKOSC_LABIRYNTU = SZEROKOSC_STRONY - 2 * MARGINES_POZIOMY;
    WYSOKOSC_LABIRYNTU = SZEROKOSC_LABIRYNTU * sqrt(3) / 2;
    MARGINES_PIONOWY = (WYSOKOSC_STRONY - WYSOKOSC_LABIRYNTU)  / 2;
    LICZBA_POZIOMOW = 61;
    BOK_KOMORKI = SZEROKOSC_LABIRYNTU / LICZBA_POZIOMOW;
    WYSOKOSC_KOMORKI = WYSOKOSC_LABIRYNTU / LICZBA_POZIOMOW;
    ODLEGLOSC_SRODKOW = WYSOKOSC_KOMORKI * 2 / 3;
    LICZBA_KOMOREK = sqr(LICZBA_POZIOMOW);
    INDEKS_WYJSCIA = LICZBA_KOMOREK - LICZBA_POZIOMOW;
    SZEROKOSC_PNIA = 30;
    WYSOKOSC_PNIA = 40;
    LICZBA_KIERUNKOW = 3;
    LEWO = 0;
    GORA_DOL = 1;
    PRAWO = 2;

type
    Kierunek = LEWO .. PRAWO;
    Komorka = record
        jestSciana : array [Kierunek] of Boolean;
        znacznik : Boolean
    end;

var
    odwiedzona : Boolean;
    komorki : array [0 .. LICZBA_KOMOREK - 1] of Komorka;

function indeks(poziom, numer : Integer) : Integer;
begin
    indeks := sqr(poziom) + numer
end;

procedure poziomNumer(indeks : Integer; var poziom, numer : Integer);
begin
    poziom := trunc(sqrt(indeks));
    numer := indeks - sqr(poziom)
end;

procedure moveto(x, y : Real);
begin
    writeln(x, ' ', y, ' moveto')
end;

procedure rmoveto(x, y : Real);
begin
    writeln(x, ' ', y, ' rmoveto')
end;

procedure rlineto(x, y : Real);
begin
    writeln(x, ' ', y, ' rlineto')
end;

procedure rysujParzystaKomorke(poziom, numer : Integer);
begin
    moveto(SRODEK_SZEROKOSCI - (poziom - numer) * BOK_KOMORKI / 2,
           WYSOKOSC_STRONY - MARGINES_PIONOWY - poziom * WYSOKOSC_KOMORKI);
    if komorki[indeks(poziom, numer)].jestSciana[LEWO] then
        rlineto(- BOK_KOMORKI / 2, - WYSOKOSC_KOMORKI)
    else
        rmoveto(- BOK_KOMORKI / 2, - WYSOKOSC_KOMORKI);
    if komorki[indeks(poziom, numer)].jestSciana[GORA_DOL] then
        rlineto(BOK_KOMORKI, 0)
    else
        rmoveto(BOK_KOMORKI, 0);
    if komorki[indeks(poziom, numer)].jestSciana[PRAWO] then
        rlineto(- BOK_KOMORKI / 2, WYSOKOSC_KOMORKI)
end;

procedure rysujLabirynt;
var i, j : Integer;
begin
    moveto(SRODEK_SZEROKOSCI - SZEROKOSC_PNIA / 2, MARGINES_PIONOWY);
    rlineto(0, - WYSOKOSC_PNIA);
    rlineto(SZEROKOSC_PNIA, 0);
    rlineto(0, WYSOKOSC_PNIA);
    for i := 0 to LICZBA_POZIOMOW - 1 do
        for j := 0 to i do
            rysujParzystaKomorke(i, 2 * j);
    writeln('stroke')
end;

function nieodwiedzonaKomorka(i, j : Integer) : Boolean;
begin
    if (i < 0) or (i > LICZBA_POZIOMOW - 1) or (j < 0) or (j > 2 * i) then
        nieodwiedzonaKomorka := false
    else
        nieodwiedzonaKomorka := komorki[indeks(i, j)].znacznik <> odwiedzona
end;

procedure sasiad(x, y : Integer; k : Kierunek; var a, b : Integer);
begin
    case k of
        LEWO : begin
            a := x;
            b := y - 1
        end;
        GORA_DOL :
            if odd(y) then begin
                a := x - 1;
                b := y - 1
            end else begin
                a := x + 1;
                b := y + 1
            end;
        PRAWO : begin
            a := x;
            b := y + 1
        end
    end
end;

function przeciwny(k : Kierunek) : Kierunek;
begin
    przeciwny := LICZBA_KIERUNKOW - 1 - k
end;

procedure przebijajSciany(x, y : Integer);
var i, pozycjaWybranego, a, b : Integer;
    s, wybrany : Kierunek;
    doSprawdzenia : array [0 .. LICZBA_KIERUNKOW - 1] of Kierunek;
begin
    komorki[indeks(x, y)].znacznik := odwiedzona;
    for s := LEWO to PRAWO do
        doSprawdzenia[s] := s;
    for i := 0 to LICZBA_KIERUNKOW - 1 do begin
        pozycjaWybranego := i + random(LICZBA_KIERUNKOW - i);
        wybrany := doSprawdzenia[pozycjaWybranego];
        doSprawdzenia[pozycjaWybranego] := doSprawdzenia[i];
        sasiad(x, y, wybrany, a, b);
        if nieodwiedzonaKomorka(a, b) then begin
            komorki[indeks(x, y)].jestSciana[wybrany] := false;
            komorki[indeks(a, b)].jestSciana[przeciwny(wybrany)] := false;
            przebijajSciany(a, b)
        end
    end
end;

procedure stworzLabirynt;
var i, x, y : Integer;
    k : Kierunek;
begin
    for i := 0 to LICZBA_KOMOREK-1 do begin
        for k := LEWO to PRAWO do
            komorki[i].jestSciana[k] := true;
        komorki[i].znacznik := false
    end;
    odwiedzona := true;
    poziomNumer(random(LICZBA_KOMOREK), x, y);
    przebijajSciany(x, y);
    komorki[INDEKS_WYJSCIA].jestSciana[GORA_DOL] := false
end;

procedure zacznijRysowanieDrogi;
begin
    moveto(SRODEK_SZEROKOSCI, MARGINES_PIONOWY - WYSOKOSC_PNIA / 2);
    rlineto(0, WYSOKOSC_PNIA / 2 + ODLEGLOSC_SRODKOW / 2)
end;

procedure rysujKrok(odbicie : Integer; k : Kierunek);
begin
    rlineto(ODLEGLOSC_SRODKOW * cos(PI * (4 * k - 1) / 6),
            odbicie * ODLEGLOSC_SRODKOW * sin(PI * (4 * k - 1) / 6))
end;

function jestRozwiazanie(x, y : Integer) : Boolean;
var znalezione : Boolean;
    k, a, b : Integer;
begin
    if not nieodwiedzonaKomorka(x, y) then
        jestRozwiazanie := false
    else begin
        komorki[indeks(x, y)].znacznik := odwiedzona;
        if indeks(x, y) = INDEKS_WYJSCIA then begin
            zacznijRysowanieDrogi;
            jestRozwiazanie := true
        end else begin
            znalezione := false;
            k := LEWO;
            while (k <= PRAWO) and not znalezione do begin
                if not komorki[indeks(x, y)].jestSciana[k] then begin
                    sasiad(x, y, k, a, b);
                    if jestRozwiazanie(a, b) then begin
                        rysujKrok((b mod 2) * 2 - 1, k);
                        znalezione := true
                    end
                end;
                k := k + 1
            end;
            jestRozwiazanie := znalezione
        end
    end
end;

procedure rozwiazLabirynt;
begin
    odwiedzona := not odwiedzona;
    writeln('[2] 0 setdash');
    if not jestRozwiazanie(0, 0) then
        writeln('% Blad algorytmu budujacego labirynt');
    writeln('stroke')
end;

begin
    randomize;
    writeln('%!PS');
    stworzLabirynt;
    rysujLabirynt;
    writeln('showpage');
    rysujLabirynt;
    rozwiazLabirynt;
    writeln('showpage')
end.
