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

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}")