Question

PROBLEMA #1972 PBINFO
VA ROG MUUULT!AM NEVOIE DE REZOLVARE IN C++
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 hambar.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 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 hambar.out 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

Answer 1

#include <iostream>

#include <fstream>

using namespace std;

ifstream f("hambar.in");

ofstream g("hambar.out");

int main()

{

int gradina[100][100]={0,0}, N, M, S=0, x, y, i, j, l, c, ok, nule;

f>>N>>M;

for(i=1;i<=M;i++){

 f>>x>>y; gradina[x][y]=1;

}

for(i=1;i<N;i++)

 for(j=1;j<N;j++)

  if(gradina[i][j]==0)

  {

   l=i; c=j;

   while(gradina[i][c+1]==0 && c+1<=N)

    c++;

   while(gradina[l+1][j]==0 && l+1<=N)

    l++;

   nule=0;

   for(x=i;x<=l;x++)

    for(y=j;y<=c;y++)

     if(gradina[x][y]==0)

      nule++;

   if(c-j+1>1 && l-i+1>1 && (c-j+1)*(l-i+1)==nule)

    if(S<nule)

     S=nule;

   j=c;

  }

g<<S;

return 0;

}