Problema ne dă un grid de $3x3$ acoperit cu 8 cuburi fiecare aşezat într-una din celule. Fiecare are două dintre feţele opuse colorate cu albastru(B) iar celelalte două colorate cu alb(W) şi cu roşu( R ) . La o mutare poate fi rostogolit unul din cuburi în celula liberă. Problema ne cere să aflăm numărul minim de mutări necesare pentru a ajunge într-o configuraţie dată. Se ştie că iniţial cuburile sunt cu faţa albă in sus iar faţa albastră e în dreapta. Celula goală se află în stânga-jos. Dacă numărul de mutări e mai mare de $30$ se va afişa $-1$

Soluţie oferită de ==user(user="freak93")==

*Soluţie oferită de ==user(user="freak93")==*

Ne vom folosi de 'Meet in the middle':blog/meet-in-the-middle făcând un bfs, fiecare nod din graf fiind o stare a gridului, din starea iniţială şi din cea finală pană la distanţa 15. La fiecare pas avem $4$ mutări posibile dintre care una ne va duce înapoi deci doar $3$ ne interesează. Astfel vom trece prin $3 ^ 15 ^$ stări.

Acesta poate fi calculat şi cu $6$ operaţii (5 înmulţiri şi o împărţire)
$x ^2^ = x × x, x ^4^ = x ^2^ × x ^2^, x ^8^ = x ^4^ × x ^4^ , x ^16^ = x ^8^ × x ^8^ , x ^32^ = x ^16^ × x ^16^ , x ^31^ = x ^32^ ÷ x$

*Soluţie*
 

Deşi iniţial pare complicată, problema se rezolvă cu o parcurgere în lăţime. Se observă că nu are sens să calculăm pentru numere mai mari de $2000$. Într-o poziţie din coadă vom reţine toate numerele folosite până la numărul curent. Când dorim să trecem într-o stare nouă trebuie doar să aplicăm operaţiile asupra ultimului număr şi al unui număr calculat pe parcurs.
==code(cpp) |