Fişierul intrare/ieşire:4x4puzzle.in, 4x4puzzle.outSursăFall Contest #2, SGU 2002
AutorMugurel Ionut AndreicaAdăugată demugurelionutMugurel-Ionut Andreica mugurelionut
Timp execuţie pe test0.35 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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.in4×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
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content