0566 - Mese

Sursa: [1]

---

Cerinţa

Gigel este patronul unui fast-food destul de cunoscut. Restaurantul are formă dreptunghiulară, și conține mai multe mese de formă de asemenea dreptunghiulară dar de dimensiuni neregulate. Gigel vă pune la dispoziție planul restaurantului, sub forma unei matrice cu n linii și m coloane, în care elementele care corespund unor spații libere sunt egale cu 0, iar elementele care fac parte din mese sunt egale cu 1. Mai precis, mesele sunt zone dreptunghiulare maximale din matrice care au toate elementele 1.

Date de intrare

Programul citește de la tastatură numerele n m, iar apoi n*m numere naturale (0 sau 1), dispuse pe n ,linii, reprezentând planul restaurantului.

Date de ieșire

Pe ecran se va afișa mesajul: "Datele de intrare corespund restricțiilor impuse.". Programul va afișa pe ecran numerele C M', separate prin exact un spațiu reprezentând numărul total de mese și suprafața maximă a unei mese. În cazul în care datele introduse de la tastatură nu îndeplinesc cerințele enunțate, programul va afișa "Datele de intrare nu corespund restricțiilor impuse.".

Restricţii şi precizări

• 1 ≤ n, m ≤ 250
• mesele nu au laturi comune
• nici o masă nu va conține spații libere
• suprafața unei mese este egală cu numărul de elemente din matrice din care este alcătuită

Exemple

Exemplu 1

Intrare

5 6

0 0 1 1 1 0

0 0 1 1 1 0

1 0 0 0 0 1

1 0 1 1 0 1

1 0 1 1 0 0

Ieșire

4 6

Rezolvare

<syntaxhighlight lang="python" line> def citire_matrice():

   try:
       n = int(input("Introduceti numarul de linii: "))
       m = int(input("Introduceti numarul de coloane: "))
       if 1 <= n <= 250 and 1 <= m <= 250:
           print("Datele sunt corecte.")
       else:
           print("Datele nu sunt conform restrictiilor impuse.")
           exit()
   except ValueError:
       print("Trebuie introduse doar numere intregi.")
       exit()

   matrice = []
   for linie in range(n):
       linie_matrice = []
       for coloana in range(m):
           try:
               valoare = int(input(f"Introduceti un numar pentru linia {linie+1}, coloana {coloana+1}: "))
               if valoare in [0, 1]:
                   print("Datele sunt corecte.")
                   linie_matrice.append(valoare)
               else:
                   print("Datele nu sunt conform restrictiilor impuse.")
                   exit()
           except ValueError:
               print("Trebuie introduse doar numere intregi.")
               exit()
       matrice.append(linie_matrice)

   return n, m, matrice

def Mese(n, m, matrice):

   a = matrice

   p = 0
   k = 0
   max_area = 0

   # function to check if a cell is inside the matrix
   def inside(i, j):
       return i >= 0 and i < n and j >= 0 and j < m

   # function to perform BFS from a cell
   def bfs(i, j):
       nonlocal a
       nonlocal max_area
       q = [(i, j)]
       area = 0
       while q:
           i, j = q.pop(0)
           if not inside(i, j) or a[i][j] != 1:
               continue
           a[i][j] = 2
           area += 1
           q.append((i - 1, j))
           q.append((i + 1, j))
           q.append((i, j - 1))
           q.append((i, j + 1))
       max_area = max(max_area, area)

   # find the maximum area of a rectangle of 1s
   for i in range(n):
       for j in range(m):
           if a[i][j] == 1:
               lat = 0
               col = 0
               while j + lat < m and a[i][j + lat] == 1:
                   lat += 1
               while i + col < n and a[i + col][j] == 1:
                   col += 1
               if lat * col > max_area:
                   max_area = lat * col

   # perform BFS from cells on the border
   for i in range(n):
       if a[i][0] == 1:
           p += 1
           bfs(i, 0)
       if a[i][m - 1] == 1:
           p += 1
           bfs(i, m - 1)
   for j in range(m):
       if a[0][j] == 1:
           p += 1
           bfs(0, j)
       if a[n - 1][j] == 1:
           p += 1
           bfs(n - 1, j)

   return p, max_area

if _name_ == '_main_':

   n, m, matrice = citire_matrice()
   p, max_area = Mese(n, m, matrice)
   print(p, max_area)

</syntaxhighlight>

Explicații

Acest cod este o implementare a problemei "Mese" - se dă o matrice binară, iar scopul este de a determina numărul de bucătării (zone de 1-uri) și aria celei mai mari bucătării.

În funcția citire_matrice(), utilizatorul este întâmpinat cu mesaje pentru a introduce numărul de linii și coloane ale matricei, iar apoi matricea propriu-zisă este citită de la tastatură. Matricea este reprezentată ca o listă de liste, fiecare listă interioară reprezentând o linie a matricei.

Funcția Mese(n, m, matrice) primește numărul de linii și coloane ale matricei și matricea însăși. În interiorul acestei funcții sunt două funcții ajutătoare:

Funcția inside(i, j) verifică dacă o anumită celulă (i, j) este în interiorul matricei, astfel încât să nu se producă erori în timpul parcurgerii matricei.
Funcția bfs(i, j) implementează o parcurgere BFS (breadth-first search) a matricei pornind de la poziția (i, j). 
Funcția explorează vecinii celulelor și marchează celulele care au fost deja explorate cu o valoare diferită de 1 sau 0 (în cazul de față, cu 2). Aria bucătăriei este calculată prin numărarea numărului de celule marcate.
Funcția principală Mese(n, m, matrice) începe prin inițializarea a trei variabile: a este o copie a matricei inițiale, p reprezintă numărul de bucătării, iar max_area este aria maximă a unei bucătării.

În prima buclă for, se parcurge matricea și se verifică câte bucătării pot fi formate din linii și coloane consecutive de 1. Se calculează aria acestora, iar dacă aria este mai mare decât aria maximă găsită până în acel moment, aceasta este actualizată.

În a doua buclă for, se caută celulele de la marginea matricei care au valoarea 1 și se pornește o parcurgere BFS de la fiecare dintre acestea. Numărul de bucătării și aria maximă a unei bucătării sunt actualizate după fiecare parcurgere BFS.

În cele din urmă, funcția returnează numărul de bucătării și aria maximă a unei bucătării, care sunt apoi afișate în funcția principală _main_.