3389 - Colturi DR

Sursă: [1]

Cerință

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_dr.in 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

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt corecte.". 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ță. În caz contrar, se va afișa pe ecran: "Datele nu sunt comform restricțiilor impuse.".

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

Exemple

Exemplu 1

colturi_dr.in

5 5

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

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

Rezolvare

def citire_matrice():
    # Deschide fișierul de intrare și citește n, m și p
    with open("colturi_dr.in", "r") as fin:
        line = fin.readline().split()
        if len(line) != 2:
            print("Datele nu sunt conform restrictiilor impuse.")
            exit()
        n, m = map(int, line)
        if not (1 <= n <= 100 and 1 <= m <= 100):
            print("Datele nu sunt conform restrictiilor impuse.")
            exit()
        matrice = []
        # Citește matricea din fișierul de intrare
        for i in range(n):
            row = list(map(int, fin.readline().split()))
            # Verifică dacă elementele matricei sunt conform cerințelor
            if not all(x in [0, 1] for x in row):
                print("Datele nu sunt conform restrictiilor impuse.")
                exit()
            matrice.append(row)
        return n, m, matrice


def colturi_dr(n, m, matrice):
    nr = 0  # Numărul dreptunghiurilor de extrem
    max_area = 0  # Aria maximă a dreptunghiului de extrem
    max_cnt = 0  # Numărul dreptunghiurilor cu aceeași arie maximă
    for i in range(n - 1):
        for j in range(m - 1):
            if matrice[i][j] == matrice[i][j + 1] == matrice[i + 1][j] == matrice[i + 1][j + 1]:
                nr += 1
                area = (i + 2) * (j + 2)
                if area > max_area:
                    max_area = area
                    max_cnt = 1
                elif area == max_area:
                    max_cnt += 1
    return nr, max_area, max_cnt


if _name_ == "_main_":
    n, m, matrice = citire_matrice()
    nr, max_area, cnt = colturi_dr(n, m, matrice)
    with open("colturi_dr.out", "w") as fout:
        fout.write(str(nr) + " " + str(max_area) + " " + str(cnt) + "\n")
    print("Numărul de dreptunghiuri de extrem este:", nr)
    print("Aria maximă a unui dreptunghi de extrem este:", max_area)
    print("Numărul de dreptunghiuri cu aceeași arie maximă este:", cnt)

Explicatie

Acest cod implementează o funcție numită citire_matrice() care citește datele de intrare dintr-un fișier colturi_dr.in. Datele de intrare conțin trei valori: n și m, reprezentând dimensiunile unei matrici de dimensiune nxm, și o matrice binară cu n linii și m coloane. Matricea este formată din 0-uri și 1-uri, și reprezintă un tip special de matrice numit "matrice de extrem" (dreptunghiurile de extrem), care conține doar dreptunghiuri cu colțurile de aceeași valoare.

Funcția citire_matrice() validează datele de intrare și returnează o tuplă formată din n, m și matricea citită.

Funcția colturi_dr() primește dimensiunile matricei și matricea în sine și calculează numărul de dreptunghiuri de extrem, aria maximă a unui dreptunghi de extrem și numărul de dreptunghiuri cu aceeași arie maximă.

În final, programul scrie datele de ieșire în fișierul colturi_dr.out și le afișează pe ecran.