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

# 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

# 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))

# Apelam functia main
if __name__ == "__main__":
    main()

</syntaxhighlight>