Atenţie! Aceasta este ultima versiune a paginii, scrisă la 2009-09-13 08:53:54.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:obmax.in, obmax.outSursăSelectie echipe ACM ICPC, UPB 2009
AutorMugurel Ionut AndreicaAdăugată demugurelionutMugurel-Ionut Andreica •mugurelionut
Timp execuţie pe test0.05 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Obmax

Intr-un tablou bidimensional cu M linii si N coloane cu elemente de 0 si de 1 sunt reprezentate mai multe obiecte. Prin obiect intelegem un grup de valori 1 alaturate pe toate directiile (o valoare 1 poate avea maxim 8 vecini). Stiind ca exista un singur obiect cu numar maxim de valori de 1, se cere:

  • Sa se evidentieze obiectul cu numar maxim de valori 1 (daca exista) folosind valori 2 (valorile 1 care-l compun se vor transforma in valori 2).
  • Sa se copieze daca este posibil obiectul maximal (cel identificat la punctul 1) intr-o alta pozitie libera (cu valori 0), inlocuind valorile 0 initiale cu valori 3. Copierea se va realiza fara rotiri sau oglindiri (deci se doreste doar o translatie a obiectului). Daca obiectul poate fi copiat in mai multe locuri, se poate alege oricare dintre variante. Pozitiile pe care se face copierea se pot invecina cu valori 1 sau 2.

Date de intrare

Fisierul de intrare obmax.in contine:

  • pe prima linie numerele M si N separate printr-un spatiu
  • urmatoarele M linii contin cate N valori de 0 si 1 (valorile de pe aceeasi linie sunt separate prin cate un spatiu)

Date de ieşire

În fişierul de ieşire obmax.out veti afisa tabloul bidimensional dat, in care obiectul cu numar maxim de valori 1 (daca exista) este marcat prin valori 2 si in care pozitiile ocupate de o copie a obiectului cu numar maxim de valori 1 (daca copierea este posibila) sunt marcate prin valori 3. Practic, se vor afisa M linii cu cate N valori fiecare, reprezentand tabloul bidimensional transformat.

Restricţii

  • 1 ≤ M,N ≤ 15

Exemplu

obmax.inobmax.out
6 8
0 0 0 0 0 1 1 0
0 1 1 1 0 0 0 0
0 1 1 0 0 0 0 1
0 1 1 1 0 0 0 1
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 1 1 0
0 2 2 2 0 0 0 0
0 2 2 0 3 3 3 1
0 2 2 2 3 3 0 1
0 0 0 0 3 3 3 0
0 0 0 0 0 0 0 0
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?