Zeď člena Edward Ploška

Edward Ploška

Právě se potýkám s algoritmem na vyřešení bludiště (rozhodl jsem se použít vlnu) nějak mi to nejde do hlavy 😣 Nemá někdo zkušenost s touto situací?

Nahoru

9.1.2023 19:39

Edward Ploška

Zasranej Petr Laštovička si myslí že něco znamená ale opak je pravdou. Je mu 43 a v životě se nedotkl ženy.🤣👌Jeho první a poslední úspěch byl v roce 2003 kdy ukradl a publikoval MŮJ KÓD PIŠKVOREK a vyhrál s ním přes 100 000kč v Microsoft soutěži. Byl bych rád kdyby se mi veřejně omluvil a byl co nejdříve ZABANOVÁN z itnetwork.

Váš přítel a učitel Edward Ploška, studujte a programujte. <3

Nahoru

4.1.2023 10:01

Edward Ploška

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.

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ám vás rád kamarádi, studujte a programujte.

Váš Edward Ploška.

Nahoru

22.11.2022 11:18

Nejčastěji vyhledáváné

Zeď člena Edward Ploška