Vizualizare sursă pentru „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>