Cod sursa(job #1300192)

Utilizator new_programmerIffi Fiffi new_programmer Data 24 decembrie 2014 04:35:50
Problema BMatrix Scor 24
Compilator cpp Status done
Runda Arhiva de probleme Marime 6.39 kb
#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;
}