== include(page="template/taskheader" task_id="cclj") ==

Neinfricatul $K0Kalaru 47$ a dat din nou lovitura. Acesta s-a calificat la renumita competitie internationala, si anume la $JBOI$. Intrucat $K0Kalaru 47$ a investit foarte mult in pregatirea sa de adevarat olimpic, acesta nu mai are cu ce sa vina la competitie, prin urmare a imprumutat un cal de la vecinul sau. $K0Kalaru 47$ nu este bun la geografie asa ca este de datoria voastra sa-l ajutati sa ajunga. Dar, ghiciti ce! El a devenit atat de bun in ultimul an incat daca acesta ajunge la competitie o sa ia $MAXIM$ (si evident primul loc). Acest lucru nu trebuie lasat sa se intample (doar echipa Romaniei are voie sa ia $MAXIM$), asa ca voi trebuie sa-i dati $K0Kalarului 47$ un traseu cat mai lung ca sa nu reuseasca sa ajunga la timp la $JBOI$. Din nefericire, pe cat de praf este el la geografie, pe atat de buna memorie are. Asa ca voi trebuie sa-i dati un traseu cat mai lung si care nu trece printr-un loc de mai multe ori (altfel acesta o sa se prinda ca l-ati masluit).
Suprafata pe care poate calatori $K0Kalaru 47$ (acesta sta cam prost cu actele de identitate si nu are voie sa paraseasca regiunea est-europeana) are forma unei table $NxM$. Calul lui Sorinel poate sa se deplaseze doar in forma de $L$ (exact cum o fac toti caii de pe lumea asta). Scopul vostru este sa generati o serie de mutari de cal cu cardinal maxim. Puteti incepe si termina oriunde, dar la punctare se va tine cont daca s-a inceput si/sau terminat in colturi.

Neînfricatul $K0Kalaru 47$ a dat din nou lovitura. Acesta s-a calificat la renumita competiţie internaţională $JBOI$. Întrucât $K0Kalaru 47$ a investit foarte mult în pregătirea sa de adevărat olimpic, acesta nu mai are cu ce să vină la competiţie, prin urmare a împrumutat un cal de la vecinul său, Sorinel. $K0Kalaru 47$ nu este bun la geografie, aşa că este de datoria voastră să-l ajutaţi să ajungă. Dar, ghiciţi ce! el a devenit atât de bun în ultimul an încât dacă acesta ajunge la competiţie o să ia $MAXIM$ (şi evident primul loc). Acest lucru nu trebuie lăsat să se întâmple (doar echipa României are voie să ia $MAXIM$), aşa că voi trebuie să-i daţi $K0Kalarului 47$ un traseu cât mai lung ca să nu reuşească să ajungă la timp la $JBOI$. Din nefericire, pe cât de praf este el la geografie, pe atât de bună memorie are. Aşa că voi trebuie să-i daţi un traseu cât mai lung şi care nu trece printr-un loc de mai multe ori (altfel acesta o să se prindă că l-aţi măsluit).
Suprafaţa pe care poate călători $K0Kalaru 47$ (acesta stă cam prost cu actele de identitate şi nu are voie să părăsească regiunea est-europeană) are formă unei table $NxM$. Calul $K0Kalarului 47$ poate să se deplaseze doar în formă de $L$ (exact cum o fac toţi caii de pe lumea asta). Scopul vostru este să generaţi o serie de mutări de cal cu cardinal maxim. Puteţi începe şi termina oriunde, dar la punctare se va ţine cont dacă s-a început şi/sau terminat în colţuri.

h2. Date de intrare

h2. Date de intrare

Fişierul de intrare $cclj.in$ contine un numar $t$ care semnfica numarul de teste. Pe urmatoarele $t$ linii se afla cate doua numere $N$ si $M$ despartite printr-un spatiu, reprezentand dimensiunea tablei.

Fişierul de intrare $cclj.în$ conţine un număr $t$ care semnfică numărul de teste. Pe următoarele $t$ linii se află câte două numere $N$ şi $M$ despărţite printr-un spaţiu, reprezentând dimensiunea tablei.

h2. Date de ieşire

h2. Date de ieşire

Fisierul de iesire $cclj.out$ contine raspunsul pentru fiecare test. Pe prima linie a fiecarui test se afla numarul $K$ ce semnifica numarul de casute prin care $K0Kalaru 47$ o sa treaca. Pe urmatoarele $N$ linii se afla cate $M$ numere ce reprezinta o matrice $A$ care codifica cele $K$ casute prin care se trece in felul urmator: drumul $K0Kalarului 47$ incepe in casuta in care $A[i][j]$ este $1$, continua unde este $2$, etc, termindanu-se unde se afla valoarea $K$. In caz ca printr-o casuta nu se trece, trebuie sa afisati $0$. In matricea $A$ nu trebui sa existe vreun numar in afara de $0$ care apare de mai multe ori. De asemenea toate numerele trebuie sa fie intregi in intervalul $[0, K]$.
 
h2. Restricţii
 
* $1 ≤ t ≤ 10$
* $8 ≤ N, M ≤ 500$
 
* **Subtask 1 (20 puncte):** $N, M ≤ 20$
* **Subtask 2 (20 puncte):** $N = M, N$ da restul $1$ la impartirea cu $4$
* **Subtask 3 (20 puncte):** $N = M, N$ este o putere de $2$
* **Subtask 4 (40 puncte):** Restrictii initiale
 
h2. Punctaj

Fişierul de ieşire $cclj.out$ conţine răspunsul pentru fiecare test. Pe prima linie a fiecărui test se află numărul $K$ ce semnifică numărul de căsuţe prin care $K0Kalaru 47$ o să treacă. Pe următoarele $N$ linii se află câte $M$ numere ce reprezintă o matrice $A$ care codifică cele $K$ căsuţe prin care se trece în felul următor: drumul $K0Kalarului 47$ începe în căsuţa în care $A[i][j]$ este $1$, continuă unde este $2$, etc, termindanu-se unde se află valoarea $K$. În caz că printr-o căsuţa nu se trece, trebuie să afişaţi $0$. În matricea $A$ nu trebui să existe vreun număr în afară de $0$ care apare de mai multe ori. De asemenea toate numerele trebuie să fie întregi în intervalul $[0, K]$.
 
h2. Restricţii
 
* $1 ≤ t ≤ 10$
* $8 ≤ N, M ≤ 500$
 
* **Full Feedback!**
* **Subtask 1 (20 puncte):** $N, M ≤ 20$
* **Subtask 2 (20 puncte):** $N = M, N$ dă restul $1$ la împărţirea cu $4$
* **Subtask 3 (20 puncte):** $N = M, N$ este o putere de $2$
* **Subtask 4 (40 puncte):** Restricţii iniţiale
 
h2. Punctaj
 
Punctajul obţinut pe un test este: <tex> punctaj = (\frac{K}{NrMax})^{2}*Pointspertest </tex>, unde $K$ este cel de mai sus, $NrMax$ este numărul maxim de căsuţe prin care se poate trece în condiţiile de mai sus, iar $Pointspertest$ reprezintă câte puncte valorează testul ( $70%$ din punctajul maxim acordat testului dacă niciunul dintre capete nu este într-un colţ, $85%$ pentru un capăt şi $100%$ pentru ambele) .
Punctajul final este suma punctajelor obţinute la fiecare test.
 
h2. Exemplu
 
table(example). |_. cclj.în |_. cclj.out |
| 2
10 10
8 9
|7
1 0 0 0 0 0 0 0 0 0
0 0 2 0 0 0 0 0 0 0
0 0 0 0 3 0 0 0 0 0
0 0 0 0 0 0 4 0 0 0
0 0 0 0 0 0 0 0 5 0
0 0 0 0 0 0 6 0 0 0
0 0 0 0 0 0 0 0 7 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
16
1 0 9 0 7 0 0 0 0
0 0 2 0 0 0 0 0 0
3 10 0 8 0 6 0 0 0
0 0 0 5 0 0 0 0 0
11 4 0 0 0 0 0 0 0
0 0 12 0 0 0 0 15 0
0 0 0 0 13 0 0 0 0
0 0 0 0 0 0 14 0 16
|

Punctajul obtinut pe un test este: <tex> punctaj = (\frac{Nr}{NrMax})^{2}*Pointspertest </tex>, unde $Nr$ este cel de mai sus, $NrMax$ este numarul maxim de casute prin care se poate trece in conditiile de mai sus, iar $Pointspertest$ rerezinta cate puncte valoreaza testul ( $7$ daca niciunul dintre capete nu este intr-un colt, $8.5$ pentru un capat si $10$ pentru ambele) .
Punctajul final este suma punctajelor obtinute la fiecare test.

h3. Explicaţie

h2. Exemplu

**Atentie!**: Exemplul nu obtine 10 puncte si nici drumurile nu au lungime optima.

table(example). |_. cclj.in |_. cclj.out |
| 1
10 10
| 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 0 0 2 0 0 0 0 0
0 0 0 0 0 0 3 0 0 0
0 0 0 0 0 0 0 0 4 0
0 0 0 0 0 0 5 0 0 0
0 0 0 0 0 0 0 0 6 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
|

În exemplu, presupunând că ar valora 10 puncte, fiecăruia din teste îi vor fi atrbuite câte 5 puncte. În acest caz la primul test se va pleca din punctajul de 0.85 * 5 = 4.25 puncte, în timp ce la al doilea test se va pleca din punctajul de 1.0 * 5 = 5 puncte.

== include(page="template/taskfooter" task_id="cclj") ==