3387 - Veverita

Cerinţa

Se dă o matrice cu n linii și m coloane cu valori de 0 și 1. Numim dreptunghi de extrem un dreptunghi ale cărui vârfuri au valori egale. Determinați numărul acestor dreptunghiuri, aria dreptunghiului de arie maximă și câte dreptunghiuri au aceeași valoare a vârfurilor ca și dreptunghiul de arie maximă.

Date de intrare

Fișierul de intrare colturi_drin.txt conține pe prima linie numărul n de linii, numărul m de coloane, iar pe următoarele linii se află cele n * m numere naturale.

Date de ieșire

Fișierul de ieșire colturi_dr.out va conține pe prima linie numerele nr, A si cnt reprezentând cele trei numere specificate în cerință.

Restricţii şi precizări

• 1 ⩽ n, m ⩽ 100
• numărul de dreptunghiuri de extrem cu vârfuri de 1 este diferit de numărul de dreptunghiuri de extrem cu vârfuri de 0.
• un dreptunghi de extrem are cel puțin două linii și două coloane

Exemplul 1

colturi_drin.txt

5 5
1  0  1  0  1
1  1  1  1  0
0  1  1  0  1
0  1  0  0  1
1  0  1  0  1

colturi_dr.out

11 25 9

Rezolvare

def count_extreme_rectangles(matrix):
    n = len(matrix)
    m = len(matrix[0])
    cnt = [0, 0]
    max_area = [0, 0]
    max_area_cnt = [0, 0]

    for i in range(n):
        for j in range(m):
            for k in range(i+1, n):
                for o in range(j+1, m):
                    if matrix[i][j] == matrix[k][o] == matrix[i][o] == matrix[k][j]:
                        cnt[matrix[i][j]] += 1
                        area = (k-i+1) * (o-j+1)
                        if area > max_area[matrix[i][j]]:
                            max_area[matrix[i][j]] = area
                            max_area_cnt[matrix[i][j]] = 1
                        elif area == max_area[matrix[i][j]]:
                            max_area_cnt[matrix[i][j]] += 1

    if max_area[0] > max_area[1]:
        return cnt[0], max_area[0], max_area_cnt[0]
    else:
        return cnt[1], max_area[1], max_area_cnt[1]


def main():
    n, m = map(int, input().split())
    matrix = [list(map(int, input().split())) for _ in range(n)]

    if n > 100 or m > 100:
        print("Datele de intrare nu corespund restrictiilor impuse")
        return

    nr, A, cnt = count_extreme_rectangles(matrix)
    print("Datele de intrare corespund restrictiilor impuse")
    print(nr, A, cnt)


if __name__ == "__main__":
    main()

Explicatie

Sunt 9 dreptunghiuri de extrem a cărui vârfuri sunt 1, respectiv 2 ale cărui vârfuri sunt 0. Dreptunghiul de extrem de arie maximă are colțul stânga sus la (0,0) și colțul dreapta jos la (5,5).