2425 - Peri

Se consideră o matrice dreptunghiulară A cu m linii şi n coloane cu valori 0 sau 1, liniile şi coloanele fiind numerotate de la 1 la m, respectiv de la 1 la n. Numim dreptunghi de colţuri (x1, y1) (x2,y2) cu x1 < x2 şi y1 < y2 mulţimea elementelor A[i][j] cu x1 ≤ i ≤ x2 si y1 ≤ j ≤ y2. Numim perimetru al dreptunghiului de colţuri (x1, y1) (x2, y2) mulţimea elementelor A[i][j] pentru care (i = x1 şi y1 ≤ j ≤ y2) sau (i = x2 şi y1 ≤ j ≤ y2) sau (j = y1 şi x1 ≤ i ≤ x2) sau (j = y2 şi x1 ≤ i ≤ x2).

Cerința

Determinaţi diferenţa maximă dintre numărul de elemente egale cu 1 şi numărul de elemente egale cu 0 aflate pe perimetrul aceluiaşi dreptunghi, precum şi numărul de dreptunghiuri pentru care se obţine această diferenţă.

Date de intrare

Fișierul de intrare peri.in conține pe prima linie numerele m şi n, separate printr-un singur spaţiu. Pe următoarele m linii este dată matricea A, numerele de pe aceeaşi linie fiind separate de câte un spaţiu.

Date de ieșire

Fișierul de ieșire peri.out va conţine o singură linie pe care se află două numere întregi separate printr-un spaţiu. Primul număr este diferenţa maximă dintre numărul de elemente 1 şi numărul de elemente 0 de pe perimetrul unui dreptunghi. Al doilea întreg este numărul de dreptunghiuri pentru care diferenţa dintre numărul de elemente 1 şi numărul de elemente 0 de pe perimetru este maximă.

Restricții și precizări

• 1 ≤ m, n ≤ 250
• Prin diferenţă nu se înţelege diferenţă în valoare absolută!

Exemplu:

peri.in

4 5
1 0 0 1 0 
0 1 1 0 0 
0 1 0 1 0 
1 1 1 0 1

peri.out

4 2

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

   m = len(matrix)
   n = len(matrix[0])
   max_diff = float('-inf')
   count_max_diff_rects = 0

   # Helper function to count 1's and 0's on the perimeter
   def count_perimeter(x1, y1, x2, y2):
       ones = 0
       zeros = 0
       for j in range(y1, y2 + 1):
           if matrix[x1][j] == 1:
               ones += 1
           else:
               zeros += 1
           if matrix[x2][j] == 1:
               ones += 1
           else:
               zeros += 1
       for i in range(x1 + 1, x2):
           if matrix[i][y1] == 1:
               ones += 1
           else:
               zeros += 1
           if matrix[i][y2] == 1:
               ones += 1
           else:
               zeros += 1
       return ones, zeros

   # Iterate over all possible top-left corners (x1, y1)
   for x1 in range(m - 1):
       for y1 in range(n - 1):
           # Iterate over all possible bottom-right corners (x2, y2)
           for x2 in range(x1 + 1, m):
               for y2 in range(y1 + 1, n):
                   ones, zeros = count_perimeter(x1, y1, x2, y2)
                   diff = ones - zeros
                   if diff > max_diff:
                       max_diff = diff
                       count_max_diff_rects = 1
                   elif diff == max_diff:
                       count_max_diff_rects += 1

   return max_diff, count_max_diff_rects

1. Exemplu de utilizare

matrix = [

   [0, 1, 0, 1],
   [1, 0, 1, 0],
   [0, 1, 0, 1],
   [1, 0, 1, 0]

]

max_diff, count_max_diff_rects = max_perimeter_diff(matrix) print(f"Diferența maximă: {max_diff}") print(f"Numărul de dreptunghiuri: {count_max_diff_rects}") </syntaxhighlight>