1267 - plaja

Cerința

O plajă poate fi văzută ca o matrice cu n linii și m coloane. Elementele matricii sunt codificate cu 0, însemnând o poziție liberă, și 1, însemnând o poziție ocupată. Să se afle aria celui mai mare dreptunghi liber din matricea dată.

Date de intrare

Fișierul de intrare plaja.in conține pe prima linie numerele n și m, iar pe următoarele n linii câte m caractere reprezentând plaja.

Date de ieșire

Fișierul de ieșire plaja.out va conține pe prima linie numărul S, reprezentând aria maximă a unui dreptunghi liber.

Restricții și precizări

• 1 ≤ n, m ≤ 1000

Exemplu:

plaja.in

5 5

11111

11000

11100

11100

11110

plaja.out

6

Explicație

1 1 1 1 1 1 1 0 0 0 1 1 1 0 0 1 1 1 0 0 1 1 1 1 0

Suprafata dreptunghiulara de aria maxima este cea ingrosata.

Rezolvare

<syntaxhighlight lang="python" line="1" start="1">

1. Functia max_rectangle calculeaza aria maxima a unui dreptunghi liber in matrice

def max_rectangle(matrix):

   # Daca matricea este goala, returnam 0
   if not matrix:
       return 0

   m = len(matrix[0])
   # Initializam inaltimea fiecarui dreptunghi cu 0
   height = [0] * (m + 1)
   ans = 0

   # Parcurgem fiecare rand din matrice
   for row in matrix:
       for i in range(m):
           # Daca elementul este 0, crestem inaltimea dreptunghiului
           height[i] = height[i] + 1 if row[i] == '0' else 0
       stack = [-1]
       for i in range(m + 1):
           # Cat timp inaltimea curenta este mai mica decat inaltimea din varful stivei
           while height[i] < height[stack[-1]]:
               # Scoatem elementul din varful stivei si calculam aria dreptunghiului
               h = height[stack.pop()]
               w = i - 1 - stack[-1]
               ans = max(ans, h * w)
           # Adaugam inaltimea curenta in stiva
           stack.append(i)
   return ans

1. Functia main citeste datele de intrare, calculeaza aria maxima si scrie rezultatul in fisierul de iesire

def main():

   with open('plaja.in', 'r') as file:
       n, m = map(int, file.readline().split())
       matrix = [list(file.readline().strip()) for _ in range(n)]
   area = max_rectangle(matrix)
   with open('plaja.out', 'w') as file:
       file.write(str(area))

1. Apelam functia main

if __name__ == "__main__":

   main()

</syntaxhighlight>