Pagini recente » Cod sursa (job #2851513) | Cod sursa (job #304359) | Cod sursa (job #1668337) | Cod sursa (job #63726) | Cod sursa (job #1840733)
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
int n,m,a[255][255],c[255][255],aux[255][255],answer,up[255],down[255],st[255],l[255],r[255];
char s[255];
int Solve(int n, int m);
void Rotate(int &n, int &m);
void dump( int n, int m) {
for (int i = 1; i <= n; ++ i) {
for (int j = 1; j <= m; ++ j) {
cerr << a[i][j] << " ";
}
cerr << "\n";
}
}
int Soldier(int a[255],int n);
void GetUpArray(int up[255],int n, int m);
int main() {
ifstream cin("bmatrix.in");
ofstream cout("bmatrix.out");
cin>>n>>m;
for(int i=1;i<=n;i++) {
cin>>s;
for(int j=1;j<=m;j++) {
a[i][j]=s[j-1]-'0';}}
answer=Solve(n,m);
Rotate(n,m);
answer=max(Solve(n,m),answer);
cout<<answer;
return 0;
}
int Solve(int n, int m) {
int answer=0;
GetUpArray(up,n,m);
Rotate(n,m);
Rotate(n,m);
GetUpArray(down,n,m);
reverse(down+1,down+1+n);
for(int i=1;i<=n;i++) {
answer=max(answer,up[i]+down[i+1]);}
return answer;}
void GetUpArray(int up[255],int n, int m) {
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) {
if(a[i][j]==1)
c[i][j]=0;
else
c[i][j]=c[i-1][j]+1;}}
for(int i=1;i<=n;i++) {
up[i]=max(up[i-1],Soldier(c[i],m));}}
int Soldier(int a[255],int n) {
int k;
st[0]=0;
k=0;
///LEFT
for(int i=1;i<=n;i++) {
while(k>0 && a[st[k]]>=a[i]) {
k--;}
l[i]=st[k];
st[++k]=i;}
k=0;
st[0]=n+1;
///RIGHT
for(int i=n;i>=1;i--) {
while(k>0 && a[st[k]]>=a[i]) {
k--;}
r[i]=st[k];
st[++k]=i;}
int answer=0;
for(int i=1;i<=n;i++) {
answer=max(answer,a[i]*(r[i]-l[i]-1));}
return answer;}
void Rotate(int &n, int &m) {
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) {
aux[j][n-i+1]=a[i][j];}}
swap(n,m);
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) {
a[i][j]=aux[i][j];}}}