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

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>