| Fişierul intrare/ieşire: | 4x4puzzle.in, 4x4puzzle.out | Sursă | Fall Contest #2, SGU 2002 |
| Autor | Mugurel Ionut Andreica | Adăugată de |  Mugurel-Ionut Andreica •mugurelionut |
| Timp execuţie pe test | 0.175 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
4x4puzzle
Micutului Gigel ii plac puzzle-urile foarte mult. Acum cateva zile a descoperit traditionalul puzzle 4×4. 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
13 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.
Date de intrare
Prima linie a fisierului de intrare 4×4puzzle.in contine numarul P de puzzle-uri descrise in continuare. Fiecare puzzle consta din 4 linii, pe care sunt afisate cate 4 numere. Inaintea descrierii fiecarui puzzle exista o linie goala.
Date de iesire
Pentru fiecare din cele P puzzle-uri veti afisa in fisierul de iesire 4×4puzzle.out cate o linie continand sirul "DA", daca puzzle-ul poate fi adus in starea finala, respectiv sirul "NU" in caz contrar.
Restrictii
- 1 ≤ P ≤ 100 000
Exemplu
| 4×4puzzle.in | 4×4puzzle.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 13 12 14 15 | NU DA |
