#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: 5578
- Reputace: 106
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