Cod sursa(job #20746)

Utilizator pocaituDavid si Goliat pocaitu Data 22 februarie 2007 00:19:12
Problema Cutii Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.11 kb
#include<fstream.h>
#include<string.h>
int i=1,px[12][8][5]={{{0,0,0,1,2},{0,0,0,1,2},{0,1,2,2,2},{0,1,2,2,2}},{{0,1,1,1,2},{0,1,2,2,2},{0,1,1,1,2},{0,0,0,1,2}},{{0,1,1,2,2},{0,0,1,1,2},{0,0,1,1,2},{0,1,1,2,2}}, {{0,1,1,1,2}}, {{0,0,1,2,2},{0,0,0,1,1},{0,0,1,2,2},{0,0,1,1,1}}, {{0,1,1,1,2},{0,0,1,2,2},{0,0,1,2,2},{0,1,1,1,2}}, {{0,1,1,1,2},{0,1,1,2,2},{0,1,1,1,2},{0,0,1,1,2},{0,1,1,2,2},{0,1,1,1,2},{0,0,1,1,2},{0,1,1,1,2}}, {{0,0,0,1,1},{0,1,1,2,2},{0,0,1,1,1},{0,0,1,1,2},{0,0,0,1,1},{0,0,1,1,2},{0,0,1,1,1},{0,1,1,2,2}},/*9*/ {{0,0,0,0,0},{0,1,2,3,4}}, {{0,0,0,1,1},{0,1,2,2,3},{0,0,1,1,1},{0,1,1,2,3},{0,0,1,1,1},{0,1,1,2,3},{0,0,0,1,1},{0,1,2,2,3}}/*11*/, {{0,1,1,1,1},{0,1,2,2,3},{0,0,0,0,1},{0,1,1,2,3},{0,0,0,0,1},{0,1,1,2,3},{0,1,1,1,1},{0,1,2,2,3}}, {{0,0,0,0,1},{0,0,1,2,3},{0,1,1,1,1},{0,1,2,3,3},{0,1,1,1,1},{0,1,2,3,3},{0,0,0,0,1},{0,0,1,2,3}}  };
int    py[12][8][5]={{{0,1,2,2,2},{0,1,2,0,0},{0,0,0,1,2},{0,0,0,-1,-2}},{{0,0,1,2,0},{0,0,-1,0,1},{0,-2,-1,0,0},{0,1,2,1,1}},{{0,-1,0,-2,-1},{0,1,1,2,2},{0,1,-1,0,-1},{0,0,1,1,2}}, {{0,-1,0,1,0}}, {{0,1,1,0,1},{0,1,2,0,2},{0,1,0,0,1},{0,2,0,1,2}}, {{0,0,1,2,2},{0,1,0,-1,0},{0,1,1,1,2},{0,-2,-1,0,-2}}, {{0,-1,0,1,-1},{0,-1,0,0,1},{0,-2,-1,0,-1},{0,1,1,2,1},{0,0,1,-1,0},{0,0,1,2,1},{0,1,-1,0,0},{0,-1,0,1,1}}, {{0,1,2,0,1},{0,0,1,0,1},{0,1,-1,0,1},{0,1,0,1,1},{0,1,2,1,2},{0,1,0,1,0},{0,1,0,1,2},{0,-1,0,-1,0}},/*9*/ {{0,1,2,3,4},{0,0,0,0,0}}, {{0,1,2,-1,0},{0,0,0,1,1},{0,1,-2,-1,0},{0,0,1,1,1},{0,1,1,2,3},{0,-1,0,-1,-1},{0,1,2,2,3},{0,0,-1,0,-1}}/*11*/, {{0,-1,0,1,2},{0,0,-1,0,0},{0,1,2,3,2},{0,0,1,0,0},{0,1,2,3,1},{0,-1,0,0,0},{0,-2,-1,0,1},{0,0,0,1,0}}, {{0,1,2,3,3},{0,1,0,0,0},{0,0,1,2,3},{0,0,0,-1,0},{0,-3,-2,-1,0},{0,0,0,0,1},{0,1,2,3,0},{0,1,1,1,1}}  };
int nr[12]={4,4,4,1,4,4,8,8,2,8,8,8},k,j,kk,ppp;
int l,n,r,h,used[100],aux,da;
//int lim1[100],lim[100],d,gas;
int v[65][2],p[65],in[65][65];
/*void verif()
{int i,j,k,kk;
 int m[5][5],maxx;
 ofstream g("pento.out");
 for(i=0;i<12;i++)
   {g<<i+1<<"**\n";
	for(k=0;k<nr[i];k++)
	{for(j=0;j<=4;j++)
	  memset(m[j],0,sizeof(m[j]));
	 for(j=0,maxx=0;j<=4;j++)
	   if(py[i][k][j]<maxx)
		maxx=py[i][k][j];

	 for(j=0;j<=4;j++)
	   m[py[i][k][j]-maxx][px[i][k][j]]=j+1;
	 for(kk=0;kk<=4;kk++)
	  {for(j=0;j<=4;j++)
		g<<m[kk][j];
	   g<<'\n';
	   }
	 g<<'\n';
	 }
	g<<"\n\n";

	}
 }  */
void afiseaza()
{int m[103][103],i,j;
 l++;

 ofstream g("pento.out");
 for(i=0;i<n;i++)
  memset(m[i],0,sizeof(m[i]));
 for(i=1;i<=h;i++)
  m[v[i][1]][v[i][0]]=p[i];
 for(i=0;i<n;i++)
  {for(j=0;j<r;j++)
   g<<m[i][j]<<" ";
   g<<"\n";
   }
 g.close();


 }
void rezolva(int colt,int k)
{int x,y,i,j,d,gasit;
 x=v[colt][0];y=v[colt][1];
 //if(ppp) return;
 for(i=0;i<12&&!ppp;i++)
  if(!used[i])
	for(j=0;j<nr[i];j++)
	  {for(d=0,gasit=1;d<5;d++)
		 if(p[in[x+px[i][j][d]][y+py[i][j][d]]])
		   {gasit=0;break;}
	  if(gasit)
	   {used[i]=1;
		for(d=0;d<5;d++)
		  p[in[x+px[i][j][d]][y+py[i][j][d]]]=i+1;
		for(d=colt;d<=h&&p[d];d++);
		if(k==11)
		  //{
		   afiseaza();
		   //ppp=1;}
		else
		  rezolva(d,k+1);
		for(d=0;d<5;d++)
			p[in[x+px[i][j][d]][y+py[i][j][d]]]=0;
		used[i]=0;
		}
	 }



}
int main()
{//verif();
 int x;
 char s[14][14];
 ifstream f("pento.in");
 /*f>>n>>r;
 p[0]=1;
 for(i=1;i<=n;i++)
  {f>>s;
   for(j=0;j<r;j++)
	if(s[j]=='1')
	{v[++h][0]=j;//retin x
	 v[h][1]=i-1;//retin y
	 }

   }*/
 n=12;r=6;
 strcpy(s[1],"110011");
 strcpy(s[2],"110011");
 strcpy(s[3],"110011");
 strcpy(s[4],"111111");
 strcpy(s[5],"111111");
 strcpy(s[6],"111111");
 strcpy(s[7],"111111");
 strcpy(s[8],"111111");
 strcpy(s[9],"110011");
 strcpy(s[10],"111011");
 strcpy(s[11],"111011");
 strcpy(s[12],"111001");
 for(i=1;i<=n;i++)
  {
   for(j=0;j<r;j++)
	if(s[i][j]=='1')
	{v[++h][0]=j;//retin x
	 v[h][1]=i-1;//retin y
	 }

   }



 p[0]=1;
 for(i=1;i<=h;i++)
  for(j=i+1;j<=h;j++)
	 if(v[i][0]>v[j][0]||(v[i][0]==v[j][0]&&v[i][1]>v[j][1]))
	   {aux=v[i][0];	v[i][0]=v[j][0];		v[j][0]=aux;
		aux=v[i][1];	v[i][1]=v[j][1];		v[j][1]=aux;
		}
 for(i=1;i<=h;i++)
   in[v[i][0]][v[i][1]]=i;

 rezolva(1,0);
 ofstream g("p.out");
 g<<l;

 return 0;
 }