Hledání nejkratší cesty v bludišti

Co si z toho odnést: mapa je pole textů, vykreslení je dvojitý cyklus a jedna podmínka na políčko. Nic víc v „grafice" není.

Co si z toho odnést: {nazvy[i],-8} v interpolaci zarovná text na osm znaků doleva. Je to zkratka za PadRight(8) a v tabulkách se hodí pořád.

Co si z toho odnést: v úzkém dungeonu je zdí tolik, že cest skoro není — hrubá síla se zdá být v pohodě. Jakmile zdi zmizí, počet cest exploduje: v otevřené jeskyni 5×5 je jich 8 512 a rekurze se zavolá přes 90 000krát. Kdyby byla jeskyně 6×6, je to přes 18 milionů volání. A přitom pořád mluvíme o mapě velké jako šachovnice pro trpaslíky.

Co si z toho odnést: fronta, množina navštívených a slovník předchůdců. Tyhle tři věci stačí na nejkratší cestu v jakémkoli bludišti.

Co si z toho odnést: BFS by na téhle mapě proletělo bažinou rovnou doprava — 5 kroků, ale cena 14. Dijkstra jde oklikou po suchu: 11 kroků a cena 11. Delší trasa může být levnější a přesně o tom je dnešní druhá polovina hodiny.

Zadání:

Bez mapy nemá smysl nic hledat. Nejdřív ji tedy nakresli a zjisti, kam se z políčka dá jít.

1. Dokonči metodu Vykresli, ať poskládá mapu z emoji ⬛ a ⬜
   💡 Poradit

   Projdi mapu dvěma cykly: vnější přes řádky, vnitřní přes sloupce.
   Pro každé políčko přidej do textu jeden emoji: if (mapa[r][s] == '#') vystup += "⬛"; else vystup += "⬜";
   Na konci každého řádku přidej odřádkování: vystup += "\n";
2. Označ start 🟩 a cíl 🟥 — pozor na pořadí podmínek
   💡 Poradit

   Start a cíl musí být otestované dřív než zeď, jinak je zeď přebije.
   if (r == start.radek && s == start.sloupec) vystup += "🟩";
else if (r == cil.radek && s == cil.sloupec) vystup += "🟥";
   Teprve pak přijde podmínka na zeď a nakonec volné políčko.
3. Dokonči metodu Sousedi a vypiš, kam se dá z políčka [2,2] jít
   💡 Poradit

   Čtyři směry si připrav jako dvě pole posunů: int[] posunR = { -1, 1, 0, 0 }; a int[] posunS = { 0, 0, -1, 1 };
   V cyklu spočítej int r = pozice.radek + posunR[i]; a int s = pozice.sloupec + posunS[i];
   Soused se počítá jen tehdy, když je uvnitř mapy a není to zeď:
   if (r >= 0 && r < mapa.Length && s >= 0 && s < mapa[0].Length && mapa[r][s] != '#')

Zadání:

Napiš hledání, které nemá žádný plán — prostě zkusí všechno. A změř, kolik práce to dá.

1. Doplň tělo rekurze Zkus: projdi sousedy, kteří ještě nejsou navštívení
   💡 Poradit

   V cyklu přes sousedy přeskoč ty, kde už jsi byl: if (navstivene.Contains(dalsi)) continue;
   Pak políčko označ, zavolej rekurzi a po návratu značku zase ukliď:
   navstivene.Add(dalsi);
Zkus(dalsi, kroku + 1, navstivene);
navstivene.Remove(dalsi);
   Bez toho úklidu bys prohledal jen jednu jedinou cestu.
2. Když jsi v cíli, započítej nalezenou cestu a vrať se
   💡 Poradit

   Úplně na začátku metody se zeptej, jestli už nejsi v cíli:
   if (pozice == cil) { pocetCest++; return; }
return; je důležité — z cíle se nikam dál nechodí.
3. Přidej počitadlo volání a výpis nejkratší nalezené cesty
   💡 Poradit

   Počitadlo zvyš hned na prvním řádku metody: pocetVolani++;
   Délku si hlídej v cíli: if (nejkratsi == -1 || kroku < nejkratsi) nejkratsi = kroku;
   Hodnota -1 znamená „zatím nic nenalezeno".
4. Přidej limit volání a pusť hledání i na otevřené jeskyni
   💡 Poradit

   Hned za pocetVolani++; přidej pojistku:
   if (pocetVolani > LIMIT) { zastaveno = true; return; }
   Pak zavolej Prozkoumej(JESKYNE, (0, 0), (4, 4), "otevřená jeskyně 5x5"); a porovnej obě čísla.

Zadání:

Teď to samé chytře. Místo zkoušení všeho se mapou šíří vlna.

1. Doplň frontu a množinu navštívených políček
   💡 Poradit

   Do fronty dej start a do navstivene ho zapiš taky:
   var fronta = new Queue<(int radek, int sloupec)>();
fronta.Enqueue(START);
   Ve smyčce while (fronta.Count > 0) ber vždy var aktualni = fronta.Dequeue(); a nové sousedy dávej na konec fronty.
2. U každého objeveného políčka si zapiš předchůdce
   💡 Poradit

   Slovník predchudce si pamatuje, odkud ses kam dostal:
   predchudce[dalsi] = aktualni;
   Zapisuj ho jen u políček, která ještě nejsou v navstivene — jinak si přepíšeš kratší cestu tou delší.
3. Poskládej cestu od cíle ke startu a vypiš počet kroků
   💡 Poradit

   Jdi od cíle po předchůdcích, dokud nedojdeš na start, a nakonec seznam otoč:
   var uzel = CIL;
while (uzel != START) { uzel = predchudce[uzel]; cesta.Add(uzel); }
cesta.Reverse();
   Počet kroků je cesta.Count - 1, protože start se jako krok nepočítá.
4. Vykresli navštívená políčka 🟦 i výslednou trasu 🟨
   💡 Poradit

   Cestu si převeď na množinu, ať se v ní rychle hledá: var trasa = new HashSet<(int radek, int sloupec)>(cesta);
   Ve vykreslování pak přidej dvě nové větve před volné políčko:
   else if (trasa.Contains(p)) vystup += "🟨";
else if (navstivene.Contains(p)) vystup += "🟦";

Zadání:

Mapa dostane bažinu. Přes ni se dá jít, ale stojí čtyřikrát víc energie.

1. Doplň cenu políčka a tabulku nejlevnějších vzdáleností
   💡 Poradit

   Cena se neplatí za krok, ale za políčko, na které vstoupíš:
   int Cena(char znak) => znak == '~' ? 4 : 1;
   Do tabulky si zapiš start s nulou: var vzdalenost = new Dictionary<(int radek, int sloupec), int> { [START] = 0 };
   Pro souseda pak spočítej int nova = vzdalenost[aktualni] + Cena(TEREN[dalsi.radek][dalsi.sloupec]);
2. Vždycky vyber nehotové políčko s nejnižší zapsanou cenou
   💡 Poradit

   Minimum najdeš obyčejným cyklem:
   var aktualni = nehotove[0];
foreach (var uzel in nehotove) if (vzdalenost[uzel] < vzdalenost[aktualni]) aktualni = uzel;
   Vybrané políčko pak vyhoď z nehotove a přidej do hotove, ať ho nezpracuješ dvakrát.
3. Novou cenu zapiš jen tehdy, když je nižší než ta dosavadní
   💡 Poradit

   Tohle je jádro celé Dijkstry:
   if (!vzdalenost.ContainsKey(dalsi) || nova < vzdalenost[dalsi])
   Uvnitř zapiš novou cenu, poznamenej předchůdce a pokud políčko ještě nikde není, přidej ho do nehotove.
4. Vypiš cenu i počet kroků a porovnej s BFS na stejné mapě
   💡 Poradit

   Celková cena už v tabulce leží: vzdalenost[CIL].
   BFS máš připravené v metodě BfsCesta() — zavolej ho a jeho cenu si dopočítej součtem cen políček na trase:
   foreach (var p in bfsCesta.Skip(1)) bfsCena += Cena(TEREN[p.radek][p.sloupec]);

Zadání:

Hrdina stojí u vchodu do dungeonu, v jeho útrobách je truhla. Naplánuj mu cestu a spočítej, co ho to bude stát.

1. Najdi hrdinovi trasu k truhle pomocí hotové metody NajdiCestu
   💡 Poradit

   Metoda už je napsaná — stačí ji zavolat a výsledek si uložit:
   var cesta = NajdiCestu();
   Vždycky ošetři případ, kdy cesta neexistuje: if (cesta.Count == 0) { ... }. Prázdný seznam znamená „truhla je zazděná".
2. Vytvoř hrdinu: jméno, životy, zlato a inventář
   💡 Poradit

   Stačí obyčejné proměnné a jeden seznam:
   string jmeno = "Arkon";
int zivoty = 100;
int zlato = 40;
var inventar = new List<string> { "Meč", "Lektvar" };
3. Každý krok ubere 2 životy, za výpravu přidej zlato a kořist
   💡 Poradit

   Počet kroků máš z délky trasy: int kroky = cesta.Count - 1;
zivoty = Math.Max(0, zivoty - kroky * 2);
zlato += 30 - kroky;
   Kořist přidej do inventáře: inventar.Add("Zlatý klíč");
4. Vypiš deník výpravy a vykresli trasu na mapě
   💡 Poradit

   Deník je obyčejný seznam vět, do kterého během výpravy přidáváš:
   var denik = new List<string>();
denik.Add($"Vyrazil jsem z [{START.radek},{START.sloupec}].");
   Na konci ho vypiš cyklem a pod něj přidej vykreslenou mapu s trasou 🟨.

Vytvoř program „Navigátor dungeonu", který na jedné mapě porovná oba chytré algoritmy:

• mapa má zdi #, suchou zem . a bažinu ~ a vykreslí se emoji,
• BFS najde trasu s nejmenším počtem kroků,
• Dijkstra najde trasu s nejnižší cenou,
• program vypíše u obou počet kroků, cenu a počet navštívených políček,
• a nakonec napíše větu, která trasa se hrdinovi víc vyplatí a proč.

Přines soubor Program.cs nebo snímek obrazovky s výstupem.

Pro rychlejší studenty, kteří dokončí cvičení dřív, nebo na posledních 10–15 minut.

Robot na mřížce je nejvhodnější, protože děti řeší přesně tu úlohu, kterou dnes programovaly — jen rukou. Kdo si to zkusí na papíře, lépe pochopí, proč BFS objevuje mapu po vrstvách.