Snake

snake

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

Într-o matrice cu obstacole există un şarpe de lungime impară $Len$. Din păcate, un muritor obişnuit nu poate vedea şarpele în totalitate, el vede doar poziţiile impare din corpul lui, poziţiile pare fiind văzute ca celule obişnuite ale matricii, fără obstacol.
Matricea este dată în fişierul de intrare având ca fiecare element una din următoarele valori:
* $-1$ - obstacol
* $0$ - poziţie liberă sau ocupată de o bucată pară din şarpe
* $x$ cu $1 ≤ x ≤ Len$ - poziţie ocupată de a $x$-a bucată din şarpe
Se cere să se reconstruiască o amplasare validă a şarpelui pe matrice. Dacă sunt mai multe solutii, se poate afişa oricare dintre ele. Se garantează că există cel putin o soluţie.

Poveste şi cerinţă...

h2. Date de intrare

Pe prima linie se găsesc numerele $N$, $M$ şi $Len$, reprezentând numărul de linii, numarul de coloane ale matricii, respectiv lungimea şarpelui.
Pe următoarele $N$ linii se află câte $M$ numere care descriu matricea ca în cerinţă.
Toate numerele impare de la $1$ la $Len$ apar exact o singură dată. Distanţa Manhattan dintre oricare două poziţii impare consecutive ale şarpelui este $2$.

Fişierul de intrare $snake.in$ ...

h2. Date de ieşire

Se va găsi matricea cu amplasarea şarpelui descrisă în totalitate.

În fişierul de ieşire $snake.out$ ...

h2. Restricţii

* $1 ≤ N, M ≤ 100$
* Pentru 20 de puncte, $1 ≤ N * M ≤ 20$
* Se garantează că există cel puţin o soluţie

* $... ≤ ... ≤ ...$

h2. Exemplu