Zdravim, potreboval by som pomoc pri rieseni jedneho algoritmu. Vstup programu je sachovnica velkost n*n a samotna sachovnica, kde su moje figurky, cierne figurky a moja kralovna + horne obmedzenie, ktore mi hovori, ze ak prekrocim dany pocet krokov tak koniec. Vystupom programu musi byt najkratsia postupnost krokov, tak aby som povyhadzoval vsetky cierne figurky. Mam pribliznu predstavu ako riesit tento problem, bude to najskor rekurzia, a na papieri mam aj rozkreslene ako by to malo fungovat. Neviem vsak, ako bude co najlepsie, z hladiska dalsich operacii, ukladat poziciu figuriek (myslim datovy typ). Momentalne som to mal v strukture, kde som mal dvojrozmerne pole, a vzdy som si vytvaral akoby sachovnicu. To ale asi nie je spravne riesenie, kedze neviem potom uplne ako prechadzat po jednotlivych stavoch. Viete mi s tymto nejak poradit?

Prečo sa ti nepozdáva dvojrozmerné pole?
Stačí ti matica n*n, to je šachovnica. Tá určuje pozíciu figúrky. To ako ju budeš reprezentovať je na tebe. Či len obyčajným číslom alebo vlastným dátovým typom.

No do tej sachovnice resp. pola som si 1ckami znacil pozicie kam sa z aktualnej pozicie mozem posunut. Nasledne by som mal prejst cez vsetky tie 1cky a zanorit sa hlbsie, teda z kazdej jednicky skontrolovat kam sa da ist a posunu sa atd atd. Problem mam v tom, ako systematicky prechadzat vsetky tie "jednicky"

V matici si ukladaj pozíciu figúriek, nie ťahy. Nasledujúce kroky si vieš vždy vypočítať z aktuálneho stavu.
Prechádzať to môžeš tou rekurziou, ako si už spomenul. Alebo si spravíš frontu neprehľadaných stavov, do ktorej budeš vkladať nové stavy a postupne ich vyberať a prechádzať.

Len tak zo zaujímavosti, aká škola?

Dakujem velmi pekne za odpoved. Mozes mi vsak este blizsie popisat ako myslis to ukladanie pozicii do 2D pola? Nejal si to neviem predstavit. Uz nad tym sedim dost dlho a nemysli mi to
Studujem v prahe na technike.

Z hľadiska štuktúry by som nevymýšľal nič náročné. Jednoduché 2D pole poslúži ako šachovnica a doň stačí ukladať čísla. Figúriek nie je nijak veľa, takže ti stačít jednoduché kódovanie na štýl
0 - prázdne
10 - biela kráľovná
20 - čierna kráľovná
11 - biely kráľ
21 - čierny kráľ
12 - biely strelec
22 - čierny strelec
atď (1 biely, 2 čierny a druhé číslo označí figúrku).

Z jedného čísla v 2D poli si vieš teda vycucať aj pozíciu, aj farbu a aj pohyb figúrky. A to ti stačí na všetky výpočty okolo.

Ďalej by som ako stav neukladal celé 2D pole, stačí pozíciu figúriek a v každej iterácií sa dá 2D pole jednoducho zostaviť a na ňom vykonať výpočty. Ale zase ak je to úloha na čas výpočtu, tak bude samozrejme lepšie ukladať ako stav celú šachovnicu. Jeden stav potom môže byť reprezentovaný troma poliami čísel - figúrka[n], X[n], Y[n] (prvá možnosť), alebo celým 2D poľom (druhá možnosť). Alebo ak sa hráme na cool programátorov, tak len jedným poľom čísel o veľkosti n*n, ktoré bude mapované ako 2D pole (index bude určovať X,Y a hodnota figúrku).

Rekurziu by som asi v tomto prípade nerobil, fronta bude jednoduchšia a na túto úlohu aj lepšia (robíš v podstate prehľadávanie do šírky).

Celkom som zo zadania necpochopil, ci ide o simulaciu hry, alebo sa len hybe bielov damou a snazi sa vyhodit cierne figurky, ktore sa nehybu. Ak to je takto reprezentacia moze byt ovela jednoduhsia a stacia na to 4 stavy.
Kedze mas zadanu maximalny pocet tahov, to je sucastne aj maximalna hlba zanorenia tak by som sa skor priklonik ku rekurzii (pokial nie je ta hlbka prilis velka v c/c++ to budu radovo stovky).

Ja som pochopil, že sa môže hýbať všetkými svojimi figúrkami. Ak iba dámou, tak sa to dá samozrejme jednoduchšie, tam je komplexita omnoho nižšia a rakurzia stačí.

Je to presne ako hovori harrison. Zaujimaju ma len cierne figurky, moje biele su len akoze prekazka. Hladam minimalnu cestu ako postupne vyhodit vsetky cierne figurky. Dakujem vsetkym za odpovede.

//autoeditácia príspevku (10 Mar 2018, 14:34)
Podarilo sa mi to rozbehat, chcel by som sa vsak este spytat na jednu vec, ktorou by som to urychlil. Neviem, ci sa tomu bude dat pochopit, ale skusim to vysvetlit. Pre zjednodusenie predpokladajme, ze sa s kralovnou viem pohybovat len doprava alebo dolava. Som v strede sachovnice, zistim, vsetky mozne policka kam sa mozem posunut. Posuvam sa najprv do lava, az narazim uplne na okraj sachovnice. Dajme tomu, ze som uplne hore v rohu. Takze suradnice (0,0). Odtial zistim, ze mozem uz ist len do prava (1,0),(2,0),(3,0).... Kedze do lava sa uz nemozem posunut idem do prava, teda na poziciu (1,0). Odtial ale zase zistim, ze mozem ist do (0,0), a nasledne zase do (1,0). A takto cyklim medzi dvomi polickami, az kym neprekrocim max hlbku. Viem toto nejak jednoducho riesit?

Pamataj si odkial si prisiel.

Tiež som to chcel napísať. Len som potom rozmýšľal, či nemôže nastať situácia kedy vrátenie sa a pokračovanie iným smerom môže byť kratším riešením.

94jakub napísal:Tiež som to chcel napísať. Len som potom rozmýšľal, či nemôže nastať situácia kedy vrátenie sa a pokračovanie iným smerom môže byť kratším riešením.

Myslim, ze moze. Mozno by som porozmyslal, ci sa to nevztahuje len na pripady, ked pohybom zobral figurku a nasledne sa moze vratit naspet.
Tiez je asi dobre orezavat hlbku rekurzie zatial najlepsim skore.