1973 - Hambar2

Enunț

Prințesa Gîrcella este foarte frumoasă. Fiindcă a venit momentul să se mărite, foarte mulți feciori au venit să îi ceară mâna. Printre aceștia se află și Cavalerul de Aur, marele algoritmician. Gîrcella îl dorește pe cel mai inteligent, așa că le va pune o provocare. Grădina sa este o matrice pătratică binară (cu valori 0 sau 1), valorile 0 reprezintă teren liber iar valorile 1 reprezintă pomi. Cel ce va găsi suprafața dreptunghică de arie maximă ce conține doar valori 0, pe care va construi un hambar, va câștiga mâna frumoasei Gîrcella.

Cerința

Ajutați-l pe Cavalerul de Aur să câștige această întrecere.

Date de intrare

Fișierul de intrare hambar2.in 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 două 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 hambar2.out va conține pe prima linie numărul S, reprezentând aria maximă a unei suprafețe dreptunghiulare.

Restricții și precizări

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

Exemplu

hambar2.in

hambar2.out

Rezolvare

<syntaxhighlight lang="python"> nMAX = 1000

def clear(stiva):

   while stiva:
       stiva.pop()

def calculate_histogram(n, mat):

   h = [0] * (n + 1)

   for i in range(1, n+1):
       for j in range(1, n+1):
           if not mat[i][j]:
               h[j] += 1
           else:
               h[j] = 0

   return h

def calculate_left_boundary(n, h):

   st = [0] * (n + 1)
   stiva = []

   for j in range(1, n+1):
       while stiva and h[stiva[-1]] >= h[j]:
           stiva.pop()

       if not stiva:
           st[j] = 0
       else:
           st[j] = stiva[-1]

       stiva.append(j)

   return st

def calculate_right_boundary(n, h):

   dr = [0] * (n + 1)
   stiva = []

   for j in range(n, 0, -1):
       while stiva and h[stiva[-1]] >= h[j]:
           stiva.pop()

       if not stiva:
           dr[j] = n+1
       else:
           dr[j] = stiva[-1]

       stiva.append(j)

   return dr

def calculate_max_rect(n, mat):

   arieMAX = 0

   h = calculate_histogram(n, mat)
   st = calculate_left_boundary(n, h)
   dr = calculate_right_boundary(n, h)

   for j in range(1, n+1):
       arieMAX = max(arieMAX, h[j] * (dr[j] - st[j] - 1))

   return arieMAX

def validate_input(n, m):

   if not 1 <= n <= 1000:
       raise ValueError("n must be between 1 and 1000")
   if not 1 <= m <= 1000:
       raise ValueError("m must be between 1 and 1000")

def main():

   with open('hambar2.in', 'r') as fin, open('hambar2.out', 'w') as fout:
       n, m = map(int, fin.readline().split())
       validate_input(n, m)

       mat = [[False] * (nMAX + 1) for _ in range(nMAX + 1)]
       for _ in range(m):
           x, y = map(int, fin.readline().split())
           mat[x][y] = True

       fout.write(str(calculate_max_rect(n, mat)))

if __name__ == '__main__':

   main()

</syntaxhighlight>

Explicație

Acest cod este o implementare Python a algoritmului de determinare a celui mai mare dreptunghi înmatriculabil într-o matrice dată. Programul primește un fișier de intrare 'hambar2.in' care conține dimensiunile matricei (n, m) și pozițiile elementelor din matrice care au valoarea True. Aceste elemente reprezintă pătrate ocupate în matrice. Scopul programului este să găsească cel mai mare dreptunghi neocupat din matrice și să returneze aria acestuia.

Algoritmul funcționează astfel:

Se calculează histograma pentru fiecare linie a matricei. Histograma reprezintă numărul de pătrate goale consecutive din fiecare linie.
Se determină limitele stângi și drepte ale fiecărei coloane a matricei, folosind stack-uri și histograma calculată anterior.
Se calculează aria fiecărui dreptunghi care are baza în fiecare coloană și înălțimea dată de histograma corespunzătoare.
Se alege cel mai mare dreptunghi dintre cele calculate.

În final, programul scrie aria dreptunghiului găsit în fișierul 'hambar2.out'.