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 plajain.txt 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 plajaout.txt 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

Exemplul 1:

plajain.txt

5 5
11111
11000
11100
11100
11110

plajaout.txt

Datele de intrare corespund restrictiilor impuse
6

Exemplul 2:

plajain.txt

plaja

plajaout.txt

Datele de intrare nu corespund restrictiilor impuse

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">

def validare(matrice, n_linii, m_coloane): # functia de validare a datelor de intrare

   if not matrice:
       raise ValueError("Matricea este goala")

   if not (1 <= n_linii <= 1000) or not (1 <= m_coloane <= 1000):
       raise ValueError("Valorile n sau m nu respecta restrictiile impuse")

   for row in matrice:
       if len(row) != m_coloane:
           raise ValueError("Lungimea randului nu este egala cu m")

       for element in row:
           if not element.isdigit():    # fiecare caracter trebuie sa fie cifra
               raise ValueError("Elementul matricei nu este o cifra")

   file_out.write("Datele de intrare corespund restrictiilor impuse\n")

def max_rectangle(matrice): # functia de rezolvare

   m_coloane = len(matrice[0])
   height = [0] * (m_coloane + 1)
   ans = 0

   for row in matrice:
       for i in range(m_coloane):
           height[i] = height[i] + 1 if row[i] == '0' else 0
       stack = [-1]
       for i in range(m_coloane + 1):
           while height[i] < height[stack[-1]]:
               h = height[stack.pop()]
               w = i - 1 - stack[-1]
               ans = max(ans, h * w)
           stack.append(i)
   return ans

if __name__ == '__main__':

   file_in = open('plajain.txt', 'r')         # declararea fisierelor
   file_out = open('plajaout.txt', 'w')       # fisierul out trebuie declarat cu optiunea "w" (write)

   try:
       n, m = map(int, file_in.readline().split())
       matrix = [list(file_in.readline().strip()) for _ in range(n)]

       validare(matrix, n, m)                 # apelul functiei de validare
       area = max_rectangle(matrix)     # apelul functiei de rezolvare
       file_out.write(str(area))

   except ValueError:
       file_out.write("Datele de intrare nu corespund restrictiilor impuse")
   except IndexError:
       file_out.write("Datele de intrare nu corespund restrictiilor impuse")

</syntaxhighlight>