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
!! 17.06.2018 (Jel.) Khanova škola zve nadšence ke spolupráci na překladech návodů pro učitele a rodiče.
! 04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
17.01.2016 (Jel.) Rok 2016 s novými a novějšími krystaly od kolegy Pavla!
17.01.2016 (Jel.) Nabídka knih z oborů matematiky, fyziky, chemie
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

matla94
Zelenáč
Příspěvky: 1
Škola: MFF UK
Pozice: student
Reputace:   
 

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: 2589
Reputace:   71 
 

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é.


Definujme pojem "definice" jen pomocí předem definovaných pojmů.

Offline

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson