1972 - Hambar

Enunț

Gigel are o grădina sub forma unei matrice binare de ordin N, unde 0 reprezintă teren liber, 1 reprezintă pomi. El dorește să construiască un hambar pe dreptunghiul de arie maximă format doar din 0.

Cerința

Ajutați-l pe Gigel să găsească dreptunghiul de arie maximă format doar din 0.

Date de intrare

Fișierul de intrare hambarin.txt conține pe prima linie numerele N și M, reprezentând dimensinunea matricei, respectiv numărul de pomi, iar pe următoarele M linii se vor găsi perechi numere x și y, separate printr-un spațiu, reprezentând indicele liniei, respectiv al coloanei pe care se află un pom.

Date de ieșire

Fișierul de ieșire hambarout.txt va conține pe prima linie numărul S, reprezentând aria maximă a unei suprafețe dreptunghiulare ce nu conține 1.

Restricții și precizări

• 1 ≤ N, M ≤ 1000
• Nu se vor afla 2 sau mai mulți pomi în același loc.

Exemplul 1

hambarin.txt

5 5

1 3

2 1

2 5

5 1

5 5

hambarout.txt

Datele introduse corespund restricțiilor impuse.

12

Exemplul 2

hambarin.txt

5 5

1 3

2 1

2 5

5 1

5 1000

hambarout.txt

Datele introduse nu corespund restricțiilor impuse.

Rezolvare

# 1972 - Hambar
def validare(dim_n1, dim_m1, lista_pomi1):           # functia de validare a datelor de intrare
    if dim_n1 < 1 or dim_n1 > 1000 or dim_m1 < 1 or dim_m1 > 1000:
        raise ValueError

    for pom in lista_pomi1:
        if pom[0] < 1 or pom[0] > dim_n1 or pom[1] < 1 or pom[1] > dim_n1:
            raise ValueError

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


def arie_maxima(dim_n1, lista_pomi1):                     # functia de rezolvare
    matrice = [[0] * dim_n1 for _ in range(dim_n1)]
    for pom in lista_pomi1:
        matrice[pom[0]-1][pom[1]-1] = 1

    dp = [[0] * dim_n1 for _ in range(dim_n1)]
    max_area = 0

    for i in range(dim_n1):
        for j in range(dim_n1):
            if matrice[i][j] == 0:
                dp[i][j] = dp[i-1][j] + 1 if i > 0 else 1

    for i in range(dim_n1):
        for j in range(dim_n1):
            width = dp[i][j]
            for k in range(i, -1, -1):
                width = min(width, dp[k][j])
                max_area = max(max_area, width * (i-k+1))

    fisier_iesire.write(str(max_area))


if __name__ == '__main__':
    fisier_intrare = open("hambarin.txt", "r")         # declararea fisierelor
    fisier_iesire = open("hambarout.txt", "w")       # fisierul out trebuie declarat cu optiunea "w" (write)

    try:
        dim_n, dim_m = map(int, fisier_intrare.readline().split())
        lista_pomi = [list(map(int, fisier_intrare.readline().split())) for _ in range(dim_m)]

        validare(dim_n, dim_m, lista_pomi)                 # apelul functiei de validare
        arie_maxima(dim_n, lista_pomi)               # apelul functiei de rezolvare

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