Fişierul intrare/ieşire:snake.in, snake.outSursăFMI No Stress 8
AutorMihai CalanceaAdăugată defminostress2018Fmi no stress 2018 fminostress2018
Timp execuţie pe test0.5 secLimită de memorie262144 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Snake

Într-o matrice cu obstacole există un şarpe de lungime impară L. Fiecare poziţie a corpului şarpelui acoperă o celulă a matricii, poziţii consecutive ale şarpelui acoperă celule adiacente în matrice, iar oricare două poziţii diferite ale şarpelui acoperă celule diferite. Şarpele nu acoperă obstacole. 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 matricei, 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 ≤ L - 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 soluţii, se poate afişa oricare dintre ele. Se garantează că există cel putin o soluţie.

Date de intrare

Fişierul de intrare snake.in conţine pe prima linie numerele N, M şi L, 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 L apar exact o singură dată. Distanţa Manhattan dintre oricare două poziţii impare consecutive ale şarpelui este 2.

Date de ieşire

Fişierul de ieşire snake.out trebuie să conţină matricea cu amplasarea şarpelui descrisă în totalitate.

Restricţii

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

Exemplu

snake.insnake.out
4 4 7
-1 3 0 0
1 0 5 0
0 0 0 0
0 0 7 0
-1 3 4 0
1 2 5 0
0 0 6 0
0 0 7 0
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?