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

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