Costel are o mare pasiune pentru rezolvarea cubului Rubik, atât de mare încât a început să facă cercetări şi calcule diverse pornind de la acest joc. Ultima lui idee, inspirată de cubul Rubik, foloseşte un cub de latură 2 unităţi, compus din 8 cuburi cu latura de o unitate (cub unitate), având feţele exterioare colorate. Fiecare cub unitate are 3 feţe exterioare şi fiecare dintre acestea este colorată cu una dintre cele 10 culori disponibile, codificate prin cifrele de la 0 la 9.
Identificarea cuburilor unitate se face conform specificaţiilor din Figura 1. Cubul care nu este vizibil în Figura 1 are coordonatele (1, 1, 2). Cubul lui Costel permite efectuarea următoarelor tipuri de mutări, asemănătoare cu cele din cubul Rubik:
M1: Paralelipipedul 1 conţine cuburile unitate de coordonate: (1, 1, 1); (1, 2, 1); (2, 1, 1); (2, 2, 1). Acesta este un disc aşezat orizontal şi poate fi rotit cu 90 de grade către dreapta, în sensul acelor de ceasornic.
M2: Paralelipipedul 2 conţine cuburile unitate de coordonate: (1, 1, 2); (1, 2, 2); (2, 1, 2); (2, 2, 2). Acesta este un disc aşezat orizontal şi poate fi rotit cu 90 de grade către dreapta, în sens invers acelor de ceasornic.
M3: Paralelipipedul 3 conţine cuburile unitate de coordonate: (1, 1, 1); (2, 1, 1); (1, 1, 2); (2, 1, 2). Acesta este un disc aşezat vertical şi poate fi rotit cu 90 de grade către planul îndepărtat, în sens invers acelor de ceasornic.
M4: Paralelipipedul 4 conţine cuburile unitate de coordonate: (1, 2, 1); (2, 2, 1); (1, 2, 2); (2, 2, 2). Acesta este un disc aşezat vertical şi poate fi rotit cu 90 de grade către planul îndepărtat, în sensul acelor de ceasornic.
Prin configuraţie se înţelege memorarea culorii fiecărei feţe exterioare a celor 8 cuburi unitate, deci culorile celor 24 de feţe exterioare. Aplicând o succesiune validă de mutări se obţine o altă configuraţie.
Pentru uşurinţa memorării unei configuraţii, Costel utilizează desfăşurarea în plan a celor 6 feţe ale cubului său după modelul din Figura 2, care ilustrează modul în care sunt dispuse feţele în desfăşurare. Fiecare faţă a cubului conţine patru feţe exterioare ale cuburilor unitate având, în ordine, coordonatele specificate în figură.
Cerinţă
Fiind date o configuraţie iniţială şi o configuraţie finală ale jocului, determinaţi numărul minim de mutări prin care se poate ajunge de la configuraţia iniţială la configuraţia finală şi succesiunea corespunzătoare de mutări prin care se poate obţine configuraţia finală.
Date de intrare
Fişierul de intrare joc21.in conţine 12 linii corespunzătoare configuraţiei iniţiale, câte două linii pentru fiecare dintre cele şase feţe; pe fiecare linie sunt memorate câte două cifre, separate prin exact un spaţiu (pe primele două linii se află elementele feţei 1, pe următoarele două linii se află elementele feţei 2, … , pe liniile 11 şi 12 se află elementele feţei 6).
Pe următoarele 12 linii se află elementele configuraţiei finale, câte două linii pentru fiecare dintre cele şase feţe; pe fiecare lnie sunt memorate câte două cifre, separate prin exact un spaţiu.
Date de ieşire
Fişierul de ieşire joc21.out va conţine pe prima linie, un număr natural MIN, reprezentând numărul minim de mutări determinat. Pe următoarele MIN linii succesiunea de mutări care transformă configuraţia iniţială în cea finală, pe fiecare linie fiind scris un număr natural cuprins între 1 şi 4 ce reprezintă numărul asociat unei mutări.
Restricţii
• Se garantează că pentru toate datele de test există soluţie, aceasta având cel mult 11 mutări.
• Orice soluţie cu număr minim de mutări care conduce la obţinerea configuraţiei finale va obţine punctajul maxim.
