Pagini recente » Cod sursa (job #10431) | Cod sursa (job #2518538) | Cod sursa (job #2829981) | Cod sursa (job #875624) | Cod sursa (job #1300192)
#include<iostream>
#include<fstream>
#define m_max 200
#define n_max 200
using namespace std;
int m, n, w[m_max+1][m_max+1][2], starton[m_max+1][2], endon[m_max+1][2], best[n_max+1];
char bmat[m_max+1][n_max+1], amat[m_max+1][n_max+1];
char t;
int temp;
int main() {
int temp, max1=-1, max2=-1, max=-1, k, i, j;
char junkchar;
ifstream in;
in.open("bmatrix.in");
in>>m>>n;
for(i=1;i<=m;i++) {
for(j=1;j<=n;j++) {
in>>bmat[i][j];
// cout<<bmat[i][j]<<" ";
}
// cout<<"\n";
}
in.close();
for(i=1;i<=m;i++) {
max1=0; max2=0;
for(k=1;k<=n;k++)
best[k]=bmat[i][k]-'0';
for(k=1;k<=n;k++)
if(best[k]==0) { //first k with 0
temp=0;
temp++;
for(++k;best[k]==0 && k<=n;k++)
temp++;
if(max1<temp) {
max2=max1;
max1=temp;
}
else if(max2<temp)
max2=temp;
} //exits k at 1
w[i][i][0]=max1;w[i][i][1]=max2;
for(j=i+1;j<=m;j++) {
max1=0; max2=0;
for(k=1;k<=n;k++)
if(best[k]==0 && bmat[j][k]-'0'==1)
best[k]=1;
for(k=1;k<=n;k++)
if(best[k]==0) { //first k with 0
temp=0;
temp++;
for(++k;best[k]==0 && k<=n;k++)
temp++;
temp*=j-i+1;
//cout<<temp<<"\n";
if(max1<temp) {
max2=max1;
max1=temp;
}
else if(max2<temp)
max2=temp;
} //exits k at 1
w[i][j][0]=max1;w[i][j][1]=max2;
}
}
endon[1][0]=w[1][1][0]; // and end above i
for(i=2;i<=m;i++) {
endon[i][0]=endon[i-1][0];
for(j=1;j<=i;j++)
if(endon[i][0]<w[j][i][0])
endon[i][0]=w[j][i][0];
}
starton[m][0]=w[m][m][0]; // and start under i
for(i=m-1;i>=1;i--) {
starton[i][0]=starton[i+1][0];
for(j=i;j<=m;j++)
if(starton[i][0]<w[i][j][0])
starton[i][0]=w[i][j][0];
}
endon[1][1]=w[1][1][1]; // and end above i
for(i=2;i<=m;i++) {
endon[i][1]=endon[i-1][1];
for(j=1;j<=i;j++)
if(endon[i][1]<w[j][i][1])
endon[i][1]=w[j][i][1];
}
starton[m][1]=w[m][m][1]; // and start under i
for(i=m-1;i>=1;i--) {
starton[i][1]=starton[i+1][1];
for(j=i;j<=m;j++)
if(starton[i][1]<w[i][j][1])
starton[i][1]=w[i][j][1];
}
max=-1;
for(i=1;i<m;i++)
if(max<endon[i][0]+starton[i+1][0])
max=endon[i][0]+starton[i+1][0];
if(max<endon[m][1]+endon[m][0])
max=endon[m][1]+endon[m][0];
for(i=m-1;i>=1;i--)
if(endon[i][0]!=endon[m][0])
if(max<endon[i][0]+endon[m][0])
max=endon[i][0]+endon[m][0];
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
if(max<w[i][j][0]+w[i][j][1])
max=w[i][j][0]+w[i][j][1];
for(i=1;i<=m;i++) {//get transpose
for(j=1;j<=n;j++) {
//t=bmat[i][j];bmat[i][j]=bmat[j][i];bmat[j][i]=t;
amat[j][i]=bmat[i][j];
//cout<<bmat[i][j]<<" ";
}
//cout<<"\n";
}
for(i=1;i<=n;i++) {//get transpose
for(j=1;j<=m;j++) {
bmat[i][j]=amat[i][j];
}
}
temp=m;m=n;n=temp;
for(i=1;i<=m;i++) {
endon[i][0]=-1;endon[i][1]=-1;starton[i][0]=-1;starton[i][1]=-1;
}
for(i=1;i<=m;i++) {
max1=0; max2=0;
for(k=1;k<=n;k++)
best[k]=bmat[i][k]-'0';
for(k=1;k<=n;k++)
if(best[k]==0) { //first k with 0
temp=0;
temp++;
for(++k;best[k]==0 && k<=n;k++)
temp++;
if(max1<temp) {
max2=max1;
max1=temp;
}
else if(max2<temp)
max2=temp;
} //exits k at 1
w[i][i][0]=max1;w[i][i][1]=max2;
for(j=i+1;j<=m;j++) {
max1=0; max2=0;
for(k=1;k<=n;k++)
if(best[k]==0 && bmat[j][k]-'0'==1)
best[k]=1;
for(k=1;k<=n;k++)
if(best[k]==0) { //first k with 0
temp=0;
temp++;
for(++k;best[k]==0 && k<=n;k++)
temp++;
temp*=j-i+1;
//cout<<temp<<"\n";
if(max1<temp) {
max2=max1;
max1=temp;
}
else if(max2<temp)
max2=temp;
} //exits k at 1
w[i][j][0]=max1;w[i][j][1]=max2;
}
}
endon[1][0]=w[1][1][0]; // and end above i
for(i=2;i<=m;i++) {
endon[i][0]=endon[i-1][0];
for(j=1;j<=i;j++)
if(endon[i][0]<w[j][i][0])
endon[i][0]=w[j][i][0];
}
starton[m][0]=w[m][m][0]; // and start under i
for(i=m-1;i>=1;i--) {
starton[i][0]=starton[i+1][0];
for(j=i;j<=m;j++)
if(starton[i][0]<w[i][j][0])
starton[i][0]=w[i][j][0];
}
endon[1][1]=w[1][1][1]; // and end above i
for(i=2;i<=m;i++) {
endon[i][1]=endon[i-1][1];
for(j=1;j<=i;j++)
if(endon[i][1]<w[j][i][1])
endon[i][1]=w[j][i][1];
}
starton[m][1]=w[m][m][1]; // and start under i
for(i=m-1;i>=1;i--) {
starton[i][1]=starton[i+1][1];
for(j=i;j<=m;j++)
if(starton[i][1]<w[i][j][1])
starton[i][1]=w[i][j][1];
}
for(i=1;i<m;i++)
if(max<endon[i][0]+starton[i+1][0])
max=endon[i][0]+starton[i+1][0];
if(max<endon[m][1]+endon[m][0])
max=endon[m][1]+endon[m][0];
for(i=m-1;i>=1;i--)
if(endon[i][0]!=endon[m][0])
if(max<endon[i][0]+endon[m][0])
max=endon[i][0]+endon[m][0];
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
if(max<w[i][j][0]+w[i][j][1])
max=w[i][j][0]+w[i][j][1];
ofstream out;
out.open("bmatrix.out");
out<<max<<"\n";
/*
for(i=1;i<=m;i++) //pana la si inclusiv
out<<endon[i][0]<<" ";
out<<"\n";
for(j=1;j<=m;j++) // de la si inclusiv
out<<starton[j][0]<<" ";
out<<"\n";
out<<"\n";
for(i=1;i<=m;i++) {
for(j=1;j<=n;j++)
out<<w[i][j][0]<<" ";
out<<"\n";
}
out<<"\n";
for(i=1;i<=m;i++) {
for(j=1;j<=n;j++)
out<<w[i][j][1]<<" ";
out<<"\n";
}
out<<"\n";*/
out.close();
return 0;
}