== include(page="template/taskheader" task_id="4x4puzzle") ==
Micutului Gigel ii plac puzzle-urile foarte mult. Acum cateva zile a descoperit traditionalul puzzle $4x4$. Acest puzzle consta din numerele de la $0$ la $15$, aranjate intr-un patrat cu $4$ linii si $4$ coloane. O mutare consta din interschimbarea a $2$ elemente adiacente pe orizontala sau verticala, cu conditia ca unul din elemente sa fie elementul $0$. Scopul puzzle-ului este de a ajunge in urmatoarea stare finala:

$
1  2  3  4
5  6  7  8
9 10 11 12
3 14 15  0
$
Fiind data starea initiala a puzzle-ului, determinati daca exista o secventa de mutari astfel incat puzzle-ul sa fie adusin starea finala.

$1  2  3  4$
$5  6  7  8$
$9 10 11 12$
$3 14 15  0$
 
Fiind data starea initiala a puzzle-ului, determinati daca exista o secventa de mutari astfel incat puzzle-ul sa fie adus in starea finala.

h2. Date de intrare

table(example). |_. 4x4puzzle.in |_. 4x4puzzle.out |
|2

1 2 3 4
5 6 7 8
9 10 11 0
12 13 14 15

1 2 3 4
5 6 7 8
9 10 11 0