Vizualizare sursă pentru „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 ==
<syntaxhighlight lang="python" line="1">
# 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")

</syntaxhighlight>