Lekce 4 - Průchod bludištěm - Theseus

V minulé lekci, Jak najít nejkratší cestu z bodu A do bodu B?, jsme si popsali algoritmus pro hledání nejkratší cesty z bodu A do bodu B se zdrojovými kódy.

Vyřešit problém bludiště musel již v řecké mytologii Theseus, který se vydal do labyrintu zabít Minotaura. V tomto úkolu mu pomohla Ariadna, která se do Thésea zamilovala. Před vstupem do labyrintu mu dala klubko nití, které Théseus za sebou rozmotával. To by mu pomohlo se jistě z labyrintu vrátit (pokud by přežil souboj s Minotaurem), ale nezajistilo by mu to nalezení Minotaurova úkrytu v bludišti. K tomu potřeboval něco jako křídu, aby si mohl označit vchody (dveře) do místností v kterých již byl.

Algoritmus je prostý. Jít náhodně někam, kde jsem ještě nebyl. Zde postupuji sever, východ, jih a západ. Pokud jsem v místnosti, odkud vedou již jen mnou označené dveře (již jsem v nich byl), namotávám nit a vracím se tak dlouho, dokud neobjevím neoznačený vchod a do něho se vydám. Tento algoritmus mi zajistí nalezení Minotaura i to, že se případně vrátím. Natažená nit (seznam místností) je výsledek.

Výsledkem tedy není nejkratší cesta, ale jedna z možných. Pro nalezení nejkratší cesty musíme použít jiný algoritmus (vlnu).

V našem programu je nit realizována zásobníkem třídy Stack. Rozbalení nitě představuje metoda Push(místnost), kde parametrem je právě navštívená místnost, kterou vložíme do zásobníku. Namotávání nitě provedeme pomocí metody Pop(), pomocí níž mažeme poslední místnost ze zásobníku. Označení navštívených místností jsem provedl tak, že místnost označím hvězdičkou. Bludiště jsem vytvořil jako textový soubor blud.txt, obsahující 5x5 místností, kde každá místnost je řetězec pěti znaků, například: v↑→00 Tato místnost vyjadřuje, že je v ní vchod (písmeno v), a že z ní vedou vchody na sever (nahoru) a na východ (doprava). Místnost s Minotaurem vypadá takto: m00↓←.

Vchody jsou uspořádány: ↑→↓← Nula znamená žádný vchod. Místnosti jsou odděleny mezerou. Navštívenou místnost označím tak, že změním první nulu na hvězdičku.

Tady je celé bludiště:

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

Zde je základní kostra programu. Celý kód si můžete stáhnout jako soubor 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();
    }
}

Měl jsi s čímkoli problém? Stáhni si vzorovou aplikaci níže a porovnej ji se svým projektem, chybu tak snadno najdeš.