Cod sursa(job #1230931)

Utilizator LiquironIvan Liviu-Marian Liquiron Data 19 septembrie 2014 13:11:33
Problema Boundingbox Scor 0
Compilator cpp Status done
Runda Infoarena Cup 2014 Marime 1.26 kb
#include <stdio.h>
#include <math.h>

FILE *f = fopen("boundingbox.in","r");
FILE *g = fopen("boundingbox.out","w"); 

int valid(int k) 
{ 
	int i,ok=1; 
	for(i=1;i<k;i++) 
		if(x[k]<=x[i]) 
			ok=0; 
		return ok; 
}

int main(){
	int t,r,c,n=0,i,j,k,lin[51],col[51],s;
	char car;
	fscanf(f,"%d",&t);
	for(i = 1;i <= t;i++) {
		fscanf(f,"%d%d",&r,&c);
		for(j = 1;j <= r;j++)
			for(k = 1;k <= c;k++) {
				fscanf(f,"%c",&car);
				if(car == '1'){
					n++;
					lin[n] = j;
					col[n] = k;
				}
			}
		s = n;
		int k1,g,lmax,lmin,cmax,cmin;
		k1 = 1;
		x[k1]=0; 
		while(k1>0) 
		{ 
			g=0; 
			while((g==0) && (x[k1]<n)) 
			{ 
				x[k1]++; 
				if(valid(k1)==1) 
					g=1; 
			}
			if(g==1)
				if(k1<=n && k1 >= 2){
					lmax = cmax = 0;
					cmin = lmin = 51;
					for(j=1;j<=k1;j++){
						if(lin[x[j]] > lmax)
							lmax = lin[x[j]];
						if(lin[x[j]] < lmin)
							lmin = lin[x[j]];
						if(col[x[j]] > cmax)
							cmax = col[x[j]];
						if(col[x[j]] < cmin)
							cmin = col[x[j]];
					}
					s += (lmax-lmin+1)*(cmax-cmin+1);
				}
				else
				{
					k1++;
					x[k1]=0;
				}
				else
					k1--;
		}
		while(s%2==0)
		{
			s/=2;
			n--;
		}
		fprintf(g,"%d/%d",s,pow(2,n));
	}
	
	
	
}