1962 - Vecini Buni

Enunt

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. Un vecin bun al elementului A[i][j] este un vecin care are aceeaşi valoare cu A[i][j].

Cerinţa

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_buni.in conține pe prima linie trei valori naturale m, n și k reprezentând numărul de linii, numărul de coloane și numărul de valori egale cu 1 din matricea A. Pe fiecare dintre următoarele k linii ale fișierului se află două valori i și j cu semnificaţia A[i][j] este egal cu 1. Aceste valori sunt date în ordinea parcurgerii matricei pe linii de la linia 1 la linia m.

Date de ieșire

Fișierul de ieșire vecini_buni.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 şi precizări

• 2 ≤ m,n ≤ 1000
• 0 ≤ k ≤ n*m
• pentru 30% dintre teste, 2 ≤ m,n ≤ 200

Exemplul 1

vecini_buni.in

3 4 7
1 3
2 1
2 4
3 1
3 4
3 3
3 2

vecini_buni.out

3 6

Explicație

Matricea A este următoarea:

 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).

Rezolvare

<syntaxhighlight lang="python" line> def count_good_neighbors(matrix):

   m = len(matrix)
   n = len(matrix[0])
   max_good_neighbors = 0
   max_good_neighbors_count = 0

   for i in range(m):
       for j in range(n):
           if matrix[i][j] == 1:
               good_neighbors = 0
               for di in [-1, 0, 1]:
                   for dj in [-1, 0, 1]:
                       if 0 <= i + di < m and 0 <= j + dj < n and matrix[i + di][j + dj] == 1:
                           good_neighbors += 1
               good_neighbors -= 1  # Exclude the element itself
               if good_neighbors > max_good_neighbors:
                   max_good_neighbors = good_neighbors
                   max_good_neighbors_count = 1
               elif good_neighbors == max_good_neighbors:
                   max_good_neighbors_count += 1

   return max_good_neighbors, max_good_neighbors_count

def main():

   # Read input
   with open("vecini_buni.in", "r") as fin:
       m, n, k = map(int, fin.readline().split())
       matrix = [[0] * n for _ in range(m)]
       for _ in range(k):
           i, j = map(int, fin.readline().split())
           matrix[i - 1][j - 1] = 1

   # Count good neighbors
   max_good_neighbors, max_good_neighbors_count = count_good_neighbors(matrix)

   # Write output
   with open("vecini_buni.out", "w") as fout:
       fout.write(f"{max_good_neighbors} {max_good_neighbors_count}\n")

if __name__ == "__main__":

   main()

</syntaxhighlight>