Pagini recente » Cod sursa (job #240473) | Cod sursa (job #695636) | Cod sursa (job #3268762) | Cod sursa (job #1541865) | Cod sursa (job #607333)
Cod sursa(job #607333)
/*
bmatrix
O((M+N)*N*M)
http://www.informatik.uni-ulm.de/acm/Locals/2003/html/judge.html
http://drdobbs.com/database/184410529
http://homeofcox-cs.blogspot.com/2010/04/max-rectangle-in-histogram-problem.html
*/
#include <fstream>
#include <stack>
#define max(a,b) ((a) > (b) ? (a) : (b))
char Mat[200][200];
unsigned char below[200][200];
int getMax(int l1,int c1,int l2,int c2)
{
for(int j=c1;j<=c2;++j)
below[l2][j] = Mat[l2][j] == '0' ? 1 : 0;
for(int i=l2 - 1;i>=l1;--i)
for(int j=c1;j<=c2;++j)
below[i][j] = Mat[i][j] == '0' ? below[i + 1][j] + 1 : 0;
int smax(-1);
for(int i=l1;i<=l2;++i)
{
std::stack <int> st;
st.push(c1);
for(int j=c1+1;j<=c2;++j)
{
if(below[i][st.top()] < below[i][j])
st.push(j);
else if(below[i][st.top()] == below[i][j])
smax = max(smax,below[i][st.top()] * (j - st.top() + 1));
else //only case left
{
int t = st.top();
do
{
smax = max(smax,below[i][st.top()] * (t - st.top() + 1));
st.pop();
}
while(!st.empty() && below[i][st.top()] >= below[i][j]);
st.push(j);
}
}
/*
- there still may be elements inside st
- key observation is that elements inside st are in strictly increasing order by their heights
*/
if(!st.empty())
{
int t = st.top();
do
{
smax = max(smax,below[i][st.top()] * (t - st.top() + 1));
st.pop();
}
while(!st.empty());
}
}
return smax;
}
int main()
{
std::ifstream f("bmatrix.in");
std::ofstream g("bmatrix.out");
int M,N; f >> M >> N;
for(int i=0;i<M;++i)
for(int j=0;j<N;++j)
f >> Mat[i][j];
//getMax(0,0,M - 1,N - 1);
int smax(-1);
for(int i=1;i<N;++i) //horizontal sweep line
{
smax = max(smax,getMax(0,0,M - 1,i - 1) + getMax(0,i,M - 1,N - 1));
}
for(int i=1;i<M;++i) //vertical sweep line
{
smax = max(smax,getMax(0,0,i - 1,N - 1) + getMax(i,0,M - 1,N - 1));
}
g << smax;
return 0;
}