====== Hledání nejkratší cesty jezdcem ======

Hledání nejmenšího počtu tahů/skoků koněm mezi dvěma zadanými políčky.

Vyvoříme si "mapu" vzdáleností. \\
Výchozí políčko ohodotíme čislem **0**. \\
Okolní políčka do kterých se dostaneme jedním skokem číslem **1**. \\
Pro jednotlivá políčka bude "mapa" obsahovat nejmenší možný počet skoků nutných k cestě do zmíněného políčka. \\
Dosud nenavštívená políčka označíme číslem **-1**. (Někdy se používá nějaké "velké" číslo, větší něž nejdelší možná cesta.) \\
Políčka kam není dovolen přístup označíme **-2**. (Můžeme zkusit obdelníkovou "ohradu" se zdí širokou jedno nebo dvě políčka.)

Pro zadané výchozí políčko vytvoříme mapu vzdáleností. \\
Až bude mapa hotová, podíváme se na vzdálenost cílového políčka. \\
Vlastně vyřešíme úlohu hledající nejkratší cestu ze zdaného políčka do všech možných cílových políček. \\
Tato úloha je stejně složitá jako hledání nejkratší cesty mezi dvěma zadanými políčky.







===== Zjednodušená verze =====

Funkce **jump (i, k, v)** predstavuje skok na souradnici (i,k). \\
Souradnice jsou od **0** do **7**, jako indexy pole v jazyce C. \\
( **i** cislo radky, **k** cislo sloupce - ale to neni v nasem programu dulezite ) \\
Posledni parametr **v** je pocet skoku od zacatku cesty. 

Pole **p** predstavuje mapu vzdalenosti.

Fukce jump nejprve overi zda souradnice (i,k) lezi na sachovnici. \\
Pokud skocime mimo sachovnici nebudeme nic delat.

<code C++>
    if (i >= 0 && i < N && k >= 0 && k < N)
</code>

Podivame se na dosavadni hodnotu v poli **p[i][k]**. \\
Pokud je to dosud nenavstivene policko, jdeme tam. \\
Pokud jsem tam jiz byli, ale hodnota v mape je vetsi nez nase **v**, take tam pujdeme. \\
Zbyvaji policka oznacena 0, 1, ... v. Tam uz zname jinou lepsi cestu. \\
A take policka oznacena **-2** (zakazana policka / prekazky). Ty take vynechame.

<code C++>
        if (p[i][k] == -1 || p[i][k] > v)
</code>

Pokud na policko pujdeme, nastavime **p[i][k] = v**. \\
Tj. na mape oznacime, ze zname cestu z vychoziho policka do policka (i,k) dlouhou **v** tahu.

Potom zkusime osm skoku do okoli. \
Ctyri skoky na souradnice **i+-2, k+-1**. \\
Ctyri skoky na souradnice **i+-1, k+-2**. \\
Vzdy to bude cesta o jeden tah delsi **v+1**.

Skaceme ponekud bez rozmyslu. \\
Mozna mimo sachovnici. \\
Mozna na policka, kam jiz zname lepsi cestu. \\
Ale o to se postara volana fukce jump.

<code C++>
const int N = 8;

int p[N][N];

void jump (int i, int k, int v)
{
    if (i >= 0 && i < N && k >= 0 && k < N)
    {
        if (p[i][k] == -1 || p[i][k] > v)
        {
            p[i][k] = v; // ulozit vzdalenost

            jump (i+2, k+1, v+1);
            jump (i+2, k-1, v+1);
            jump (i-2, k+1, v+1);
            jump (i-2, k-1, v+1);

            jump (i+1, k+2, v+1);
            jump (i+1, k-2, v+1);
            jump (i-1, k+2, v+1);
            jump (i-1, k-2, v+1);

            // jump ( cislo radky, cislo sloupce, soucasna delka cesty )
        }
    }
}
</code>

Mapu vzdalenosti inicializujeme na hodnoty **-1** (nenavstivena policka). \\
Zvolime vychozi souradnici x0, y0 a provedeme ** jump (x0, y0, 0) **. \\
Posledni nula oznacuje hodnotu, kterou ulozime do mapy na pozici startovniho policka.

<code C++>
int main()
{
    for (int i = 0; i < N; i++)
        for (int k = 0; k < N; k++)
            p[i][k] = -1; // -1 ... nenavstivena policka
    
    int x0 = 0; // vychozi souradnice
    int y0 = 0;
    jump (x0, y0, 0);
}
</code>


===== Vytiskneme mapu vzdáleností =====

<code C++>
    for (int i = 0; i < N; i++)
    {
        for (int k = 0; k < N; k++)
        {
            if (p[i][k] == -1)
                cout << "."; // nenavstivene policko 
            else
                cout << p[i][k]; // pocet skoku od vychoziho dopicka
            cout << " ";
        }
        cout << endl; // konec radky
    }
</code>

<code>
0 3 2 3 2 3 4 5
3 4 1 2 3 4 3 4
2 1 4 3 2 3 4 5
3 2 3 2 3 4 3 4
2 3 2 3 4 3 4 5
3 4 3 4 3 4 5 4
4 3 4 3 4 5 4 5
5 4 5 4 5 4 5 6
</code>




===== Pokud něco nefunguje =====

Funkce jump rekurzive vola mnoho dalsi funkci jump. \
To se spatne krokuje v debuggeru. \\
Mnohdy pomuze omezit hloubku rekurze.

Napr. Funce jump pro v=0, zavola osm funkci jump (v=1) a ty zavolaji dalsi jump (v=2). \\
A dalsi volani jiz neprovedeme a podivame se na mapu. 

Vlastne resime ulohu pro cesty dlouhe nejvyse dva skoky. \\
Policka na ktera se nelze dostat dvema skoky zustanou oznacena jako nenavstivena (nedostupna).

<code C++>
const int limit = 2;
</code>

<code C++>
    if (i >= 0 && i < N && k >= 0 && k < N && v <= limit)
</code>

<code>
0 . 2 . 2 . . .
. . 1 2 . . . .
2 1 . . 2 . . .
. 2 . 2 . . . .
2 . 2 . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
</code>





===== Zapamatujeme si cestu zpět =====

Predchozi program uklada do mapy delku cesty. \\
Pokud je v mape kladne cislo vime, ze cesta existuje. \\
Ale nemame nikde cestu ulozenu. 

Vytvorime dve pole **zx**, **zy** skladujici souradnice odkud jsme prisli. \\
Pokud navstivime policko **(i,k)** a do tohoto policka jsme prisli z policka **(i0,k0)**, nastavime \\

<code C++>
    zx[i][k] = i0;
    zy[i][k] = k0;
</code>

Tedy **zx[i][k]** obsahuje "i souradnici", \\
**zy[i][k]** obsahuje "k souradnici", \\
ze ktere jsme se na policko (i,k) prisli.

( Pole **zx** a **zy** obsahuji informaci o jedne z moznych cest. ) \\
( Cest stejne delky muze byt vice. ) \\
( Pole **zx[i,k]** a **zy[i,k]** obsahuji informaci prave o te ceste, jejiz delka je ulozena do **p[i][k]** ). 

Pro startovaci policko a pro nevstivena policka do  **zx** a **zy**  ulozime **-1**. 

Upravy naseho programu: \\
- Pridame pole zx, zy. \\
- Funkci jump pridame parametry **i0** a **k0** oznacujici policko odkud jsme prisli. \\
- Do pole **zx** a **zy** ulozime **i0** a **k0**. \\
- Nasledujici skokum predame **i** a **k** jako adresu jejich predchudcu.

<code C++>
int zx[N][N];
int zy[N][N];

void jump(int i, int k, int v, int i0, int k0)
// skoc na (i,k) a je to v-ty skok, skaceme z (i0, k0)
{
    if (i >= 0 && i < N && k >= 0 && k < N)
    {
        if (p[i][k] == -1 || p[i][k] >= v)
        {
            p[i][k] = v;
            zx[i][k] = i0; // ulozit zpatecni cestu
            zy[i][k] = k0;

            jump (i+2, k+1, v+1, i, k);
            jump (i+2, k-1, v+1, i, k);
            jump (i-2, k+1, v+1, i, k);
            jump (i-2, k-1, v+1, i, k);

            jump (i+1, k+2, v+1, i, k);
            jump (i+1, k-2, v+1, i, k);
            jump (i-1, k+2, v+1, i, k);
            jump (i-1, k-2, v+1, i, k);

            // jump ( cilove souradnice, soucasna delka cesty, souradnice odkud skaceme )
        }
    }
}
</code>

Pole **zx** a **zy** inicializujeme na **-1** ( = neni zadne predchozi policko ). \\
Skok na pocatecni policko **x0, y0**, vzdalenost **0** a predchazejici souradnice **-1, -1**.

<code C++>
int main()
{
    for (int i = 0; i < N; i++)
        for (int k = 0; k < N; k++)
        {
            p[i][k] = -1;
            zx[i][k] = -1;
            zy[i][k] = -1;
        }

    jump(x0, y0, 0, -1, -1); 
    /* -1, -1 ... zacatek cesty ... neni zadny skok zpet */
}
</code>





===== Hledáme cestu zpět a zabloudíme =====

Funkci zadame souradnici **i, k** a chceme vytisknout cestu na toto policko. 

Podivame se do poli **zx** a **zy**, tam nalezneme souradnici predchoziho policka. \\
Pokud tam nalezneme **-1, -1** jsme na konci (cesty).

<code C++>
void bad_search (int i, int k)
{
    while (i >= 0 && k >= 0)
    {
        cout << i << "," << k << endl;
        i = zx[i][k];
        k = zy[i][k];
    }
}
</code>

<code C++>
    bad_search (N-1, N-1);
</code>

Zkusime vytisknout cestu do praveho dolniho rohu. \\
Cesta konci polickem 7,7. \\
Na toto policko jsme prisli z policka 6,5.

<code>
7,7
6,5
4,3
3,1
1,3
2,2
3,0
4,1
3,2

4,1
3,2

4,1
3,2

4,1
3,2

... atd
</code>




===== Hledáme cestu zpět  =====

Uz to vidime, zmenili jsem promennou **i** a potom jsme se podivali na jine policko **zy[i][k]**. \\
Obvykla chyba, nejak ji opravime.

<code C++>
void correct_search (int i, int k)
{
    while (i >= 0 && k >= 0)
    {
        cout << i << "," << k << endl;
        int t = zx[i][k]; // promennou i jeste budeme potrebovat
        k = zy[i][k];
        i = t;
    }
}
</code>

<code C++>
    correct_search (N-1, N-1);
</code>

<code>
7,7
6,5
4,4
6,3
4,2
2,1
0,0
</code>


===== Hledáme cestu zpět rekurzivně =====

Stejna funkce, ale rekurzivne.

<code C++>
void recursive_search (int i, int k)
{
    if (i >= 0 && k >= 0)
    {
        cout << i << "," << k << endl;
        recursive_search (zx[i][k], zy[i][k]); // zde si promennou i neznicime
    }
}
</code>



===== Ale já nechci cestu od konce k začátku =====

Nejprve vytiskneme predchozi casti cesty. \\
Az potom pridame nase policko. \\

<code C++>
void search (int i, int k)
{
    if (i >= 0 && k >= 0)
    {
        search (zx[i][k], zy[i][k]);
        cout << i << "," << k << endl;
    }
}
</code>

Vystup by mel byt jiz v uzitecnem tvaru.

<code>
0,0
2,1
4,2
6,3
4,4
6,5
7,7
</code>

===== Celý program =====

<code C++>
#include <iostream>
using namespace std;

const int N = 8;
const int limit = 100;

int p[N][N];
int zx[N][N];
int zy[N][N];

void jump(int i, int k, int v, int i0, int k0)
// skoc na (i,k) a je to v-ty skok, skaceme z (i0, k0)
{
    if (i >= 0 && i < N && k >= 0 && k < N && v <= limit)
    {
        if (p[i][k] == -1 || p[i][k] > v)
        {
            p[i][k] = v;
            zx[i][k] = i0;
            zy[i][k] = k0;

            jump (i+2, k+1, v+1, i, k);
            jump (i+2, k-1, v+1, i, k);
            jump (i-2, k+1, v+1, i, k);
            jump (i-2, k-1, v+1, i, k);

            jump (i+1, k+2, v+1, i, k);
            jump (i+1, k-2, v+1, i, k);
            jump (i-1, k+2, v+1, i, k);
            jump (i-1, k-2, v+1, i, k);
        }
    }
}

void search (int i, int k)
{
    if (i >= 0 && k >= 0)
    {
        search (zx[i][k], zy[i][k]);
        cout << i << "," << k << endl;
    }
}

int main()
{
    for (int i = 0; i < N; i++)
        for (int k = 0; k < N; k++)
        {
            p[i][k] = -1;
            zx[i][k] = -1;
            zy[i][k] = -1;
        }

    jump (0, 0, 0, -1, -1);

    for (int i = 0; i < N; i++)
    {
        for (int k = 0; k < N; k++)
        {
            if (p[i][k] == -1)
                cout << ".";
            else
                cout << p[i][k];
            cout << " ";
        }
        cout << endl;
    }

    cout << "--------" << endl;

    search (N-1, N-1);

    cout << "O.K." << endl;
}

</code>


===== Zobrazení pomocí Qt =====

Jen pro ilustraci. 

Zdrojové texty v GITu http://gitlab.fjfi.cvut.cz/culikzde/zalg/-/tree/master/jezdec-qt

Nebo jako .ZIP soubor http://kmlinux.fjfi.cvut.cz/~culikzde/zalg/2020/jezdec-qt.zip


Na posuvniku nastavime limit pro delku cesty. \\
Ve dvou mensich editacnich prvcich nastavime vychozi policko. \\
Stiskneme tlacitko "Run".


Na leve schovnici se zobrazi mapa vzdalenosti. \\
Prostredni strom zobrazuje jednotlive volani funce **jump**. \\
Pokud ve stromu vybereme polozku, na prave strane se zobrazi mapa vzdalenosti pri vstupu do funkce **jump**.


{{zalg:jezdec-zacatek.png}}

<code C++>
void Jezdec::jump (int i, int k, int v, int i0, int k0)
{
    if (i >= 0 && i < N && k >= 0 && k < N && v <= limit)
    {
        if (p[i][k] == -1 || p[i][k] > v && ! udelej_chybu)
        {
            QTreeWidgetItem * save = top; // uloz soucasnou pozici ve stromu
            MyItem * q = zobrazStav (i, k, v, i0, k0); // vytvor ve stromu novy uzel

            top = q; // nyni k zobrazovani pouzivej novy uzel

            p[i][k] = v; // zapamatuj si cestu zpet

            jump (i+2, k+1, v+1, i, k);
            jump (i-2, k+1, v+1, i, k);
            jump (i+2, k-1, v+1, i, k);
            jump (i-2, k-1, v+1, i, k);

            jump (i+1, k+2, v+1, i, k);
            jump (i-1, k+2, v+1, i, k);
            jump (i+1, k-2, v+1, i, k);
            jump (i-1, k-2, v+1, i, k);

            top = save; // navrat na puvodni pozici ve stromu
        }
    }
}
</code>





==== Chybná podmínka =====

Pokud budeme skákat jen na dosud nenavšívená políčka.

<code C++>
        if (p[i][k] == -1)
</code>

Podivejte se na zelene oznacene policko obsahujici **3**.

Navic pokud je vychozi policko na hlavni diagonale, mela by mapa byt symetricka podle teto diagonaly.

{{zalg:jezdec-spatne.png}}

Pri vetsim poctu skoku vzniknnou izolovana mista, kam se jezdec jiz nedostane.

{{zalg:jezdec-ostruvky.png}}








==== Správný postup =====

<code C++>
 if (p[i][k] == -1 || p[i][k] > v)
</code>

Poznámka: podobné podmínky se vyskytují i v obecnějších algoritmech.

Dijkstrův algoritmus https://cs.wikipedia.org/wiki/Dijkstr%C5%AFv_algoritmus#Pseudok%C3%B3d_%E2%80%93_Pascal

<code C++>
             alt = d[u] + l(u, v);
             if (alt < d[v])              
             {
                 d[v] = alt;
             }
</code>

Floydův–Warshallův algoritmus http://cs.wikipedia.org/wiki/Floyd%C5%AFv%E2%80%93Warshall%C5%AFv_algoritmus

Ve vysledne mape na leve strane je v zelene oznacenem policku jiz spravna hodnota **1**. \\
Na prave strane vidime, ze tam chviku byla honota **3** a potom jsme nasli lepsi cestu.

{{zalg:jezdec-dobre.png}}

Kompletni vysledek bez omezeni poctu skoku.

{{zalg:jezdec-vysledek.png}}