Cod sursa(job #1300079)

Utilizator new_programmerIffi Fiffi new_programmer Data 24 decembrie 2014 00:26:36
Problema BMatrix Scor 44
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.41 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], maxi[m_max+1], maxj[m_max+1], best[n_max+1];
char bmat[m_max+1][n_max+1];



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;

			if(maxj[j]<max1)
				maxj[j]=max1;
		}
	}

	maxj[1]=w[1][1][0];

	for(i=n;i>=1;i--) {
		max=-1;
		for(j=i;j<=n;j++)
			if(max<w[i][j][0])
				max=w[i][j][0];
		if(i<n && max<maxi[i+1])
			max=maxi[i+1];
		maxi[i]=max;
	}

	max=-1;
	for(i=1;i<m;i++)
		if(max<maxj[i]+maxi[i+1])
			max=maxj[i]+maxi[i+1];

	ofstream out;
	out.open("bmatrix.out");
	out<<max<<"\n";/*
	for(i=1;i<=m;i++)
		out<<maxj[i]<<" ";
	out<<"\n";
	for(j=1;j<=n;j++)
		out<<maxi[i]<<" ";
	
	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;
}