Cod sursa(job #208781)

Utilizator za_wolfpalianos cristian za_wolf Data 18 septembrie 2008 13:47:49
Problema Datorii Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include<stdio.h>
#include<string.h>
#define NMAX 64
int i,j,n,m,k,l,sol,ns,z[NMAX],y[NMAX];
char c,x[NMAX][NMAX],s[NMAX],rez[NMAX];
void versol()
{
	if (ns+1<sol)
		sol=ns+1;
/*	if (sol==13)
		printf("%s\n",s);
	strcpy(rez,s);
	if (s[0]=='C')
		s[0]=='C'; */
}
void concat(int p)
{
	int tt,ww,i,j,l,t;
	char w[NMAX],x1[NMAX],x2[NMAX];
	i=ns;
	j=0;

	for (l=ns+1;l>=0;l--)
	{
		tt=-1;
		for (t=ns-l+1;t<=ns;t++)
		{
			x2[++tt]=s[t];
			x2[tt+1]=NULL;
		}

		for (t=0;t<l;t++)
		{
			x1[t]=x[p][t];
			x1[t+1]=NULL;
		}
		if (strcmp(x1,x2)==0)
		{
			j=l;
			l=0;
		}

	}
	strcpy(w,s);
	if (ns==-1)
		ww=0;
	else
		ww=1;
	for (l=j;l<=z[p];l++)
	{
		s[ns+l-j+ww]=x[p][l];
		s[ns+l-j+1+ww]=NULL;
	}
	ns=strlen(s)-1;
}
void back(int k)
{
	char qq[NMAX];
	if (k==n+1)
	{
		versol();
		return ;
	}
	int q;
	q=strlen(s);
	if (q>sol)
		return ;
	for (int i=1;i<=n;i++)
	if (!y[i])
	{
		strcpy(qq,s);
		concat(i);
		y[i]=1;
		back(k+1);
		y[i]=0;
		strcpy(s,qq);
		ns=strlen(s)-1;
	}

}
int main()
{
	freopen("dna.in","r",stdin);
	freopen("dna.out","w",stdout);
	scanf("%d%c",&n,&c);
	sol=1000;
	for (i=1;i<=n;i++)
	{
		gets(x[i]);
		z[i]=strlen(x[i])-1;
	}
	ns=-1;
	back(1);
	printf("%d\n",sol);
//	printf("%s",rez);
	return 0;
}