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 05. 11. 2018 18:41
Pruchod sachovnici - algo
Dobry den, napadlo me resit to pomoci toku, ale nedokazu s tim hnout. Vedel by nekdo? Dekuji.
Je dána šachovnice n×n, kde některá políčka jsou nepřístupná.
Celý dolní řádek je obsazen figurkami, které se mohou hýbat o jedno pole dopředu,
šikmo vlevo dopředu, či šikmo vpravo dopředu. V jednom tahu se všechny figurky
naráz pohnou (mohou i zůstat stát na místě), na jednom políčku se však musí
vyskytovat nejvýše jedna figurka. Ocitne-li se figurka na některém políčku horního
řádku šachovnice, zmizí. Navrhněte algoritmus, který najde minimální počet tahů
takový, že z šachovnice dokážeme odstranit všechny figurky, případně oznámí, že
řešení neexistuje.
Offline
#2 06. 11. 2018 22:29
- check_drummer
- Příspěvky: 4623
- Reputace: 99
Re: Pruchod sachovnici - algo
Ahoj, asi bych si ke každé překžce doplnil další pomocné překážky, na které kdyby figurka vstoupila, tak úlohu nevyřešíme. Např. je-li nějaká překážka tvořena několika poli vedle sebe ve vodorovném směru, pak jako překážku označíme i nějkterá pole pod touto vodorovnou překážkou.
A pak už bude asi řešení libovolné přípustné.
"Máte úhel beta." "No to nemám."
Offline