Fişierul intrare/ieşire:vecini.in, vecini.outSursăOJI 2009 clasa a 8-a
AutorProf. Delilah FloreaAdăugată deMstar_AngelComan Mara Mstar_Angel
Timp execuţie pe test1.7 secLimită de memorie512 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise

Vecini (clasa a 8-a)

Se consideră matricea A ale cărei elemente pot avea doar valorile 0 sau 1 şi în care numerotarea liniilor şi numerotarea coloanelor începe de la 1. Pentru un element oarecare al matricei, definim noţiunea de vecin ca fiind acele elementele din matrice aflate în imediata sa apropiere pe una dintre direcţiile orizontală, verticală sau pe cele două diagonale (vezi figura de mai jos în care s-au marcat cu x vecinii elementului marcat cu o). Un vecin bun al elementului A[i][j] este un vecin care are aceeaşi valoare cu A[i][j].

Cerinţă

Dându-se matricea A, să se determine numărul maxim de vecini buni pe care îi are unul dintre elementele matricei precum şi numărul de elemente care au acest număr maxim de vecini buni.

Date de intrare

Fişierul de intrare vecini.in conţine pe prima linie trei valori naturale m n k reprezentând numărul de linii, numărul de coloane şi respectiv numărul de valori egale cu 1 din matricea A. Pe fiecare dintre următoarele k linii se află două valori i si j cu semnificaţia A[i][j] este egal cu 1. Aceste valori sunt date in ordinea parcurgerii matricei pe linii de la linia 1 la linia m.

Date de ieşire

Fişierul de ieşire vecini.out va conţine pe prima linie două numere naturale x şi y separate printr-un singur spaţiu: x va reprezenta numărul maxim de vecini buni pe care îi are unul dintre elementele matricei date, iar y va reprezenta numărul de elemente din matricea dată care au acest număr maxim de vecini buni.

Restricţii

  • 2 <= m,n <= 1000
  • 0 <= k <= n*m/2+1
  • Pentru 30% dintre teste 2 <= m,n <= 200

Exemplu

vecini.invecini.outExplicatii
3 4 7
1 3
2 1
2 4
3 1
3 4
3 3
3 2
3 6
matricea A este urmatoarea:
0 0 1 0
1 0 0 1
1 1 1 1
Numărul maxim de vecini buni pe care îl întâlnim pentru elementele matricei este 3. Sunt 6 elemente care au acest număr maxim de vecini buni, cele situate în poziţiile: 1,2; 2,2; 2,3; 2,4; 3,2; 3,3 (cele care sunt subliniate în reprezentarea de mai sus a matricei).
Trebuie sa te autentifici pentru a trimite solutii. Click aici