F - Kolíkový solitérČasový limit: 4s, Pamäťový limit: 64MiBProgramovacie jazyky: Pascal, C, C++, Java, C++0x, Python 3.4, Python 3.11Počet bodov: 1 [ Pošli riešenie ] [ Tvoje riešenia ] [ Správne riešenia ] [ Vzorové riešenie ] Trojuholníkový kolíkový solitér sa hrá na trojuholníkovej hracej doske obsahujúcej 15 otvorov. Na začiatku hry je vo všetkých otvoroch, okrem jedného, zastrčený kolík (viď. obrázok). Každý otvor má nanajvýš šesť susedných otvorov (vpravo hore, vpravo, vpravo dole, vľavo hore, vľavo, vľavo dole). Jeden ťah hry pozostáva z vybratia kolíka v niektorom smere susediaceho s iným kolíkom, za ktorým je v tom istom smere prázdny otvor. Vybraný kolík sa presunie na ten prázdny otvor a susediaci kolík, ktorý sme ,,preskočili'' sa odstráni z hry. Cieľom hry je, aby nám na hracej doske ostal jediný kolík. ÚlohaDaná je počiatočná pozícia prázdneho otvoru a požadovaná koncová pozícia posledného kolíka. Nájdite príslušnú postupnosť ťahov, ktorá ju vyrobí, prípadne vypíšte, že taká neexistuje.VstupPrvý riadok vstupu obsahuje počet vstupných sád T (1 ≤ T ≤ 20). Každá vstupná sada je zapísaná na samostatnom riadku, obsahujúcom dve medzerou oddelené označenia pozícií - počiatočnej pozície prázdneho otvoru a koncovej pozície posledného kolíka. Pozície sú označené dvojicou malé písmeno (stĺpec) a číslo (riadok), viď. nasledovný obrázok.VýstupVýstup by mal pre každú vstupnú sadu obsahovať jeden riadok s postupnosťou 13 ťahov, ktorá premení danú počiatočnú pozíciu na danú koncovú pozíciu. Ak taká postupnosť neexistuje, daný riadok by mal obsahovať len text ,,Neda sa'' (bez úvodzoviek). Jednotlivé ťahy by mali byť oddelené medzerami. Jeden ťah sa skladá z označenia pozície vybraného kolíka a pozície prázdneho otvoru, kam sa vybraný kolík presúva, oddelených pomlčkou.PríkladVstup2 a4 c5 a1 c3 Výstupa2-a4 c3-a3 e5-c3 b2-d4 c5-c3 a5-c5 d5-b5 d4-b2 b5-b3 b2-b4 a4-a2 a1-a3 a3-c5 Neda sa |