Fişierul intrare/ieşire:dreptunghiuri5.in, dreptunghiuri5.outSursă.com 2012 Runda 2
AutorEugenie Daniel PosdarascuAdăugată deedp100Edp100 edp100
Timp execuţie pe test0.2 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Dreptunghiuri5

Se da o matrice cu N linii si M coloane plina cu 0 si 1. Se cere sa se afle cate dreptunghiuri maximale exista. Un dreptunghi maximal este o submatrice a matricii date care este plina cu 0 si are proprietatea ca nu se mai poate extinde. O submatrice se poate extinde daca cel putin una din laturile ei are ca vecini doar casute cu 0.

Date de intrare

Fişierul de intrare dreptunghiuri5.in va contine pe prima linie 2 numere naturale N si M. Pe urmatoarele N linii se vor afla cate M numere care descriu matricea.

Date de ieşire

Fişierul de ieşire dreptunghiuri5.out va contine un singur numar care reprezinta numarul de dreptunghiuri maximale din matricea data.

Restricţii

  • 1 ≤ N ≤ 1000
  • 1 ≤ M ≤ 1000

Exemplu

dreptunghiuri5.indreptunghiuri5.out
3 4
0 1 0 0
1 0 0 0
0 0 1 0
6
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content