3389 - Colturi DR

From Bitnami MediaWiki
Revision as of 11:20, 29 April 2023 by AndorGiulia (talk | contribs) (Pagină nouă: 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...)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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.