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.