Matematické Fórum
Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.
Nástěnka
❗22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
❗04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
❗23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.
Nejste přihlášen(a). Přihlásit
#1 08. 11. 2011 18:03
Cesta sachovym kralem
Ahoj, mam tu taky program:
Program bude hledat nejkratší cestu šachovým králem na šachovnici 8x8, kde na některá políčka nelze vstoupit.
Vstup programu obsahuje popořadě:
počet překážek
souřadnice jednotlivých překážek (dvojice čísel v rozsahu 1..8)
souřadnice výchozího políčka
souřadnice cílového políčka
Počet překážek je zapsán na samostatném řádku, souřadnice jsou vždy zapsány jako dvojice čísel na jednom řádku oddělená mezerou.
Výstup je buď -1, pokud král na cílové políčko nemůže dojít NEBO počet kroků, které musí vykonat.
Příklad vstupu:
1
2 1
1 1
2 2
Odpovídající výstup:
1
A potrebovala by som pomoc, nechcem, aby mi niekto napisal zdrojak, iba ak by sa nasiel niekto, kto vysvetli nejaky princip. Malo by sa to dat pomocou algoritmu vlny, ale neda sa to aj inak? Nejak menej zlozito? V pascale samozrejme. Dakujem za pomoc
Offline
#2 08. 11. 2011 20:13
- check_drummer
- Příspěvky: 5511
- Reputace: 106
Re: Cesta sachovym kralem
Ahoj. A algoritmus vlny je složitý? To máš za půl hodinky napsané.
"Máte úhel beta." "No to nemám."
Offline
#3 08. 11. 2011 20:34
Re: Cesta sachovym kralem
↑ check_drummer:
Keby som programovala uz nejaky ten rok tiez by som povedala, ze je to lahke a ze to za pol hodinky niekto napise. Ale na zaciatku nie je nikto genius...aspon vacsina ludi. Preto som len poprosila o vysvetlenie, ako sa to vlastne robi...
Offline
#4 08. 11. 2011 20:42
Re: Cesta sachovym kralem
To je jednoduchý příklad procházení grafu do šířky (vlnou).
Což je poměrně základní algoritmus, který najdeš v mnoha knížkách a bude určitě i někde na netu. S maximální složitostí počet hran + počet vrcholů, což je v podstatě lineární a to je rychlé dost.
V případě čtvercové sítě by možná šlo zjistit zda se dá jít z jednoho bodu do druhého možná i jinak. Napadá mne třeba jen projít y překážky a testovat zda neuzavírají jeden z těch bodů do nějaké části. Ovšem tam by asi bylo moc testování okolních bodů. Ovšem budeš mít jistější, rychlejší a správné, když si naimplementuješ tu vlnu.
Algoritmus vlny znáš, nebo ho chceš vysvětlit? Nebo jen pomoci naimplementovat?
Offline
#6 08. 11. 2011 21:22 — Editoval jindra (08. 11. 2011 21:26)
Re: Cesta sachovym kralem
Pascal není moje hobby, takže to zkusím obecně. Kdyžtak řekni já to zkusím sesmolit i v pascalu.
Potřebuješ dvourozměrné pole o velikosti [8][8] (šachovnici)
Potom potřebuješ frontu o velikosti 8*8. Což může být pole, nebo spojový seznam. Podstatné je že na jeden konec přidáváš a z druhého bereš. Do fronty se bude dávat záznam (v pacalu tuším record) kde budou souřadnice.
Načteš vstup do té šachovnice. Třeba 0 = prázdné a 1 = překážka 2 = navštíveno.
Do fronty vložíš startovní pozici.
Nyní si uděláš cyklus, který se bude opakovat tak dlouho dokud je něco v zásobníku.
Když doběhne, podíváš se jestli byl cílový vrchol navštíven nebo ne. Podle toho zjistíš zda se tam dá dostat.
Vlna dělá tohle:
Podívá se jestli jde o cílové políčko. Pokud ano, označí ho že tam byl, vyprázdní frontu a skončí.
Podívá se jestli je na políčku překážka nebo jestli bylo políčko navštíveno. Když ano, nic neudělá a skončí.
Když není, označí se že bylo navštíveno, přidá do fronty všechny okolní pole. Což v případě čtvercové sítě není problém, ale pozor na to aby ses nedostala za velikost šachovnice.
skončí
edit: +Si ještě uděláš proměnou pro uložení cílové lokace, pro rychlou kontrolu
Offline