Fișierul intrare/ieșire vecini.in, vecini.out Sursă OJI 2009 clasa a 8-a
Autor Delilah Florea Adăugată de avatar Mstar_Angel Coman Mara Mstar_Angel
Timp de execuție pe test 1.7 sec Limită de memorie 512 KB
Scorul tău N/A Dificultate N/A
open book Poți vedea testele pentru această problemă accesând atașamentele .

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.in vecini.out Explicatii
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 să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 2 categorii