Pagini recente » Cod sursa (job #193613) | Cod sursa (job #1639242) | Cod sursa (job #662309) | Cod sursa (job #1639790) | Cod sursa (job #2255056)
#include <fstream>
#include <stack>
using namespace std;
ifstream fin ("bmatrix.in");
ofstream fout ("bmatrix.out");
void Read ();
void Solve ();
int GetMaxArea (int [], int);
void DisplayAnswer ();
int N, M, m[1005][1005], f[1005][1005], answer;
int main()
{
Read();
Solve();
DisplayAnswer();
}
void Read ()
{
fin >> N >> M;
for (int i=1; i<=N; ++i)
{
char c[1005];
fin >> c;
for (int j=0; j<M; ++j)
m[i][j+1]=c[j]-'0';
}
}
void Solve ()
{
for (int i=1; i<=N; ++i)
for (int j=1; j<=M; ++j)
{
if (m[i][j]==0)
f[i][j]=1+f[i-1][j];
else
f[i][j]=0;
}
int H[1005]={0};
for (int i=1; i<=N; ++i)
{
for (int j=1; j<=M; ++j)
H[j]=f[i][j];
answer=max(answer, GetMaxArea(H, M+1));
}
}
int GetMaxArea (int hist[], int n)
{
// Create an empty stack. The stack holds indexes
// of hist[] array. The bars stored in stack are
// always in increasing order of their heights.
stack<int> s;
int max_area = 0; // Initalize max area
int tp; // To store top of stack
int area_with_top; // To store area with top bar
// as the smallest bar
// Run through all bars of given histogram
int i = 1;
while (i < n)
{
// If this bar is higher than the bar on top
// stack, push it to stack
if (s.empty() || hist[s.top()] <= hist[i])
s.push(i++);
// If this bar is lower than top of stack,
// then calculate area of rectangle with stack
// top as the smallest (or minimum height) bar.
// 'i' is 'right index' for the top and element
// before top in stack is 'left index'
else
{
tp = s.top(); // store the top index
s.pop(); // pop the top
// Calculate the area with hist[tp] stack
// as smallest bar
area_with_top = hist[tp] * (s.empty() ? i :
i - s.top() - 1);
// update max area, if needed
if (max_area < area_with_top)
max_area = area_with_top;
}
}
// Now pop the remaining bars from stack and calculate
// area with every popped bar as the smallest bar
while (s.empty() == false)
{
tp = s.top();
s.pop();
area_with_top = hist[tp] * (s.empty() ? i :
i - s.top() - 1);
if (max_area < area_with_top)
max_area = area_with_top;
}
return max_area;
}
void DisplayAnswer ()
{
fout << answer;
}