👤

C++
#1267
Cerința

O plajă poate fi văzută ca o matrice cu n linii și m coloane. Elementele matricii sunt codificate cu 0, însemnând o poziție liberă, și 1, însemnând o poziție ocupată. Să se afle aria celui mai mare dreptunghi liber din matricea dată.
Date de intrare

Fișierul de intrare plaja.in conține pe prima linie numerele n și m, iar pe următoarele n linii câte m caractere reprezentând plaja.
Date de ieșire

Fișierul de ieșire plaja.out va conține pe prima linie numărul S, reprezentând aria maximă a unui dreptunghi liber.
Restricții și precizări

1≤n,m≤103


Exemplu

plaja.in

5 5
11111
11000
11100
11100
11110

plaja.out

6

Explicație

1 1 1 1 1
1 1 0 0 0
1 1 1 0 0
1 1 1 0 0
1 1 1 1 0

Suprafata dreptunghiulara de aria maxima este cea ingrosata.


Răspuns :

#include <bits/stdc++.h> using namespace std; int n,m,x,maxx; char v[10001]; int v1[10001]; int get(int vec[], int k){ stack<int> s; int maxa = 0, tp, awt, i = 0; while (i < k){ if (s.empty() || vec[s.top()] <= vec[i]) s.push(i++); else { tp = s.top(); s.pop(); awt = vec[tp] * (s.empty() ? i : i - s.top() - 1); if (maxa < awt) maxa = awt; } } while (!s.empty()){ tp = s.top(); s.pop(); awt = vec[tp] * (s.empty() ? i : i - s.top() - 1); if (maxa < awt) maxa = awt; } return maxa; } int main(){ ifstream in("plaja.in"); ofstream out("plaja.out"); in>>n>>m; for(int j = 0; j <= n; ++j){ in.getline(v, 10001); for(int i = 0; i < (int)strlen(v); ++i) { if((v[i] - '0') == 1) v1[i] = 0; else if((v[i] - '0') == 0) v1[i] += 1; } x = get(v1, m); if(x > maxx) maxx = x; } out<<maxx; return 0; }
Vă mulțumim pentru vizita pe site-ul nostru dedicat Informatică. Ne dorim ca informațiile furnizate să vă fi fost utile. Dacă aveți întrebări sau aveți nevoie de suport suplimentar, nu ezitați să ne contactați. Revenirea dumneavoastră ne bucură, iar pentru acces rapid, adăugați-ne la favorite!


Ze Lesson: Alte intrebari