Editing 2425 - Peri

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

= Cerința =
Determinaţi diferenţa maximă dintre numărul de elemente egale cu <code>1</code> şi numărul de elemente egale cu <code>0</code> 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 <code>peri.in</code> conține pe prima linie numerele <code>m</code> şi <code>n</code>, separate printr-un singur spaţiu. Pe următoarele <code>m</code> linii este dată matricea <code>A</code>, numerele de pe aceeaşi linie fiind separate de câte un spaţiu.
= Date de ieșire =
Fișierul de ieșire <code>peri.out</code> 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 <code>1</code> şi numărul de elemente <code>0</code> de pe perimetrul unui dreptunghi. Al doilea întreg este numărul de dreptunghiuri pentru care diferenţa dintre numărul de elemente <code>1</code> şi numărul de elemente <code>0</code> de pe perimetru este maximă.

= Restricții și precizări =

* <code>1 ≤ m, n ≤ 250</code>
* Prin diferenţă nu se înţelege diferenţă în valoare absolută!

= Exemplu: =
<code>peri.in</code>
 4 5
 1 0 0 1 0 
 0 1 1 0 0 
 0 1 0 1 0 
 1 1 1 0 1
<code>peri.out</code>
 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

# 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>