Priechod bludiskom - Theseus

Vyriešiť problém bludisko musel už v gréckej mytológii Theseus, ktorý sa vydal do labyrintu zabiť Minotaura. V tejto úlohe mu pomohla Ariadna, ktorá sa do Thésea zamilovala. Pred vstupom do labyrintu mu dala klbko nití, ktoré Théseus za sebou rozmotával. To by mu pomohlo sa iste z labyrintu vrátiť (ak by prežil súboj s Minotaurom), ale nezabezpečilo by mu to nájdenie Minotaurova úkrytu v bludisku. K tomu potreboval niečo ako kriedu, aby si mohol označiť vchody (dvere) do miestností v ktorých už bol.

Algoritmus je prostý. Ísť náhodne niekam, kde som ešte nebol. Tu postupujem sever, východ, juh a západ. Ak som v miestnosti, odkiaľ vedú už len mnou označené dvere (už som v nich bol), namotávajú niť a vraciam sa tak dlho, kým neobjavíte neoznačený vchod a do neho sa vydám. Tento algoritmus mi zaistí nájdenie Minotaura aj to, že sa prípadne vrátim. Natiahnutá niť (zoznam miestností) je výsledok.

Výsledkom teda nie je najkratšia cesta, ale jedna z možných. Pre nájdenie najkratšej cesty musíme použiť iný algoritmus ( vlnu).

V našom programe je niť realizovaná zásobníkom triedy Stack. Rozbalenie nite predstavuje metóda Push (miestnosť), kde parametrom je práve navštívené miestnosť, ktorú vložíme do zásobníka. Namotávaní nite vykonáme pomocou metódy Pop (), pomocou ktorej natierame posledné miestnosť zo zásobníka. Označenie navštívených miestností som vykonal tak, že miestnosť označím hviezdičkou. Bludisko som vytvoril ako textový súbor blud.txt, obsahujúci 5x5 miestností, kde každá miestnosť je reťazec piatich znakov, napríklad: v ↑ → 00 Táto miestnosť vyjadruje, že je v nej vchod (písmeno v), a že z nej vedú vchody na sever (hore) a na východ (doprava). Miestnosť s Minotaurom vyzerá takto: M00 ↓ ←.

Vchody sú usporiadané: ↑ → ↓ ← Nula znamená žiadny vchod. Miestnosti sú oddelené medzerou. Navštívenú miestnosť označím tak, že zmením prvý nulu na hviezdičku.

Tu je celé bludisko:

00→↓0 00→↓← 00→↓← 00→0← 0000←
0↑→↓0 0↑0↓← 0↑000 00→↓← 0↑00←
0↑0↓0 0↑0↓0 000↓0 0↑→↓0 m00↓←
0↑→00 00→↓← 0↑→↓← 0↑00← 0↑0↓←
v↑→00 0↑00← 0↑→00 0↑00← 0↑000

Tu je základná kostra programu. Celý kód si môžete stiahnuť ako súbor Bludiste.cs.

using System.IO;
using System.Collections;
using System.Drawing;
using System.Reflection;

class Bludiste
{
    private static string[,] bludiste = new string[5, 5];
    private static Stack nit = new Stack();
    private static bool existDvere;

    #region nacteni ze souboru
    private static void nactiBludiste(bool zeSouboru)
    {
        if (zeSouboru)
        {
            // Textový soubor můžeme umístit k exe souboru bin\Debug
            //string path = "blud.txt";

            // Zde je součástí Solution
            string path =             Path.Combine(Directory.GetParent(System.IO.Directory.GetCurrentDirectory()).Parent.FullName, @"Data\blud.txt");

            try
            {
                using (StreamReader sr = new StreamReader(path))
                {
                    bool pokracovat = true;

                    for (int j = 0; j < 5; j++)
                    {
                        string radek = sr.ReadLine();
                        int cz = 0;
                        for (int i = 0; i < 5; i++)
                        {
                            while (pokracovat)
                            {
                                char znak = radek[cz];
                                bludiste[i, j] = bludiste[i, j] + znak;
                                if (znak == ' ') { pokracovat = false; cz--; }
                                cz = cz + 1;
                            }
                            cz = cz + 1;
                            pokracovat = true;
                            Console.Write(bludiste[i, j] + ' ');
                        }
                        Console.WriteLine();
                    }
                    Console.WriteLine();
                }
            }
            catch (Exception e)
            {
                Console.WriteLine("Došlo k chybě: {0}", e.ToString());
                Console.ReadKey();
            }
        }
        else
        {
            Console.WriteLine();
            Console.WriteLine("Místnosti označené hvězdičkou byly navštíveny");
            Console.WriteLine();
            for (int j = 0; j < 5; j++)
            {
                for (int i = 0; i < 5; i++)
                {
                   Console.Write(bludiste[i, j] + ' ');
                }
                Console.WriteLine();
            }
            Console.WriteLine();
        }
    }
    #endregion

    #region nalezení počátku
    private static Point najdiPocatek()
    {
        Point bunka = new Point() ;

        for (int i = 0; i < 5; i++)
        {
            for (int j = 0; j < 5; j++)
            {
                if (bludiste[i, j].Substring(0, 1) == "v")
                {
                   bunka.X = i;
                   bunka.Y = j;
                }
            }
        }
        return bunka;
    }
    #endregion

    #region Hledání cesty
    private static bool cestaNaSever(Point bunka)
    {
        bool moznost = false;
        int i = bunka.X;
        int j = bunka.Y;
        if (bludiste[i , j].Substring(1, 1) == "↑" && bludiste[i, j-1].Substring(0, 1) != "*"
            && bludiste[i, j-1].Substring(0, 1) != "v")
        {
            moznost = true;
        }
        return moznost;
    }

    //Podobně další směry

    private static void hledejCestu(Point vstupDoBludiste)
    {
        nit.Push(vstupDoBludiste);
        Point aktualniKomnata = vstupDoBludiste;
        int i;
        int j;
        bool nalezen = false;
        while (!nalezen)
        {
            //Console.WriteLine(aktualniKomnata);
            existDvere = false;
            aktualniKomnata = (Point)nit.Peek();
            if (cestaNaSever(aktualniKomnata))
            {
                existDvere = true;
                aktualniKomnata = (Point)nit.Peek();
                i = aktualniKomnata.X;
                j = aktualniKomnata.Y;
                j--;
                if (bludiste[i, j].Substring(0, 1) == "m") { nalezen = true; }
                else
                {
                    string obsahKomnaty = bludiste[i, j];
                    obsahKomnaty = obsahKomnaty.Remove(0, 1);
                    obsahKomnaty = obsahKomnaty.Insert(0, "*");
                    bludiste[i, j] = obsahKomnaty; //nahradí 0 znakem * - označení přítomnosti v komnatě
                }
                aktualniKomnata.X = i;
                aktualniKomnata.Y = j;
                nit.Push(aktualniKomnata);
                //Console.Write(aktualniKomnata + " ");
                continue;
            }

            if (cestaNaVychod(aktualniKomnata))
            {
                existDvere = true;
                aktualniKomnata = (Point)nit.Peek();
                i = aktualniKomnata.X;
                j = aktualniKomnata.Y;
                i++;
                if (bludiste[i, j].Substring(0, 1) == "m") { nalezen = true; }
                else
                {
                    string obsahKomnaty = bludiste[i, j];
                    obsahKomnaty = obsahKomnaty.Remove(0, 1);
                    obsahKomnaty = obsahKomnaty.Insert(0, "*");
                    bludiste[i, j] = obsahKomnaty; //nahradí 0 znakem * - označení přítomnosti v komnatě
                }


                aktualniKomnata.X = i;
                aktualniKomnata.Y = j;
                nit.Push(aktualniKomnata);
                //Console.Write(aktualniKomnata + " ");
                continue;
            }
        // Další směry jsou stejné

    #endregion

    #region vypisNit
    #endregion

    public static void Main()
    {
        nactiBludiste(true);
        Point vstupDoBludiste = najdiPocatek();
        hledejCestu(vstupDoBludiste);
        vypisNit(nit);
        nactiBludiste(false);
        Console.ReadKey();
    }
}