Cerința
Gigel, un personaj cunoscut, vrea de data aceasta să își construiască o casă. Astfel, el cumpără un teren, reprezentat sub forma unei matrice binare cu n linii și m coloane, dar datorită lipsei de experiență în tranzacții imobiliare este păcălit, deoarece există pe teren zone afectate în care nu se poate construi, marcate în matrice cu 0. Celelalte zone în care se poate construi sunt marcate cu 1.
Gigel acceptă că a greșit și nu are altceva de făcut decât să își construiască casa unde este posibil. Acesta caută pe terenul achiziționat o bucată de teren pătrată de dimensiune cât mai mare, pentru care toate zonele ce o alcătuiesc să fie utilizabile(marcate cu 1 în matricea binară a reprezentării terenului), în care își va construi casa.
Acesta nu se descurcă singur și vă roagă pe voi să îl ajutați să își rezolve această problemă.
Date de intrare
Fișierul de intrare terencasa_low.in conține pe prima linie numerele n m, iar apoi n șiruri cu câte m valori de 0 sau 1 reprezentând elementele matricei reprezentării binare a terenului.
Date de ieșire
Fișierul de ieșire terencasa_low.out va conține pe prima linie numărul L, reprezentând dimensiunea bucății de teren pe care își va construi Gigel casa, iar pe a 2-a linie 4 numere naturale separate prin câte un spațiu reprezentând coordonatele colțului stânga sus, respectiv dreapta jos a submatricei care corespunde bucății de teren.
Restricții și precizări
1 ≤ n , m ≤ 1000- dacă există mai multe submatrice de dimensiune maximă, Gigel o va alege pe cea care are coordonatele colțului stânga sus(implicit și ale celui dreapta jos) mai mici.
- Prin bucată de teren cât mai mare se înțelege o submatrice care respectă proprietatea din enunț(este alcătuită exclusiv din elemente cu valoarea
1) și are număr maxim de elemente.
Exemplul 1:
terencasa_low.in
5 5 0 1 1 0 1 1 1 0 1 0 0 1 1 1 0 1 1 1 1 0 1 1 1 1 1
terencasa_low.out
3 3 2 5 4
Explicație
În fișierul de intrare există o singură submatrice de dimensiune maximă. Aceasta are dimensiunea 3 și colțurile de coordonate 3 2, respectiv 5 4.
Exemplul 2:
terencasa_low.in
6 6 1 1 1 0 1 0 1 1 1 0 0 0 1 1 1 0 0 0 0 1 0 1 1 1 0 0 0 1 1 1 0 0 1 1 1 1
terencasa_low.out
3 1 1 3 3
Explicație
În fișierul de intrare există 2 submatrice de dimensiune maximă. Dimensiunea acestora este 3, iar coordonatele minime sunt 1 1, respectiv 3 3.
Cum e corect?
cout < "As la info";
cout << "As la info";
cout >> "As la info";
Felicitări! Poți mai mult?
Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.
Greșit, dar nu-i bai!
Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.
Rezolvare
Iată rezolvarea de 100 de puncte pentru problema TerenCasa_low:
#include <bits/stdc++.h>
using namespace std;
ifstream f("terencasa_low.in");
ofstream g("terencasa_low.out");
int a[1024][1024], s[1024][1024], n, m, S, l1, c1, l2, c2, i, j, maxx=1;
bool verif(int i1, int i2, int j1, int j2)
{
S = s[i2][j2] - s[i1 - 1][j2] - s[i2][j1 - 1] + s[i1 - 1][j1 - 1];
if(S == ((i2 - i1 + 1) * (i2 - i1 + 1))) return true;
return false;
}
void Maxim()
{
for(int i1 = 1; i1 < n; i1++)
for(int j1 = 1; j1 < m; j1++)
for(int i2 = i1 + maxx, j2 = j1 + maxx; i2 <= n && j2 <= m; i2++, j2++)
if(verif(i1, i2, j1, j2))
{
if(i2 - i1 + 1 > maxx)
{
maxx = i2 - i1 + 1;
l1 = i1;
l2 = i2;
c1 = j1;
c2 = j2;
}
}
else break;
}
int main()
{
f >> n >> m;
for(i = 1; i <= n; i++)
for(j = 1; j <= m; j++)
{
f >> a[i][j];
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
}
Maxim();
g << maxx << '\n' << l1 << " " << c1 << " " << l2 << " " << c2 << '\n';
f.close();
g.close();
return 0;
}Atenție
Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa 
.
Rezolvarea problemei #3475 TerenCasa_low
Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #3475 TerenCasa_low de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.
Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!