Editing 3389 - Colturi DR

Sursă: [pbinfo.ro/probleme/3389/colturi-dr]
== 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 ==
<syntaxhighlight lang="python" line="1">
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)
</syntaxhighlight>
== 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.