#include<stdio.h>
#include<string.h>
static int f[6],ff[6];
char init[]="ABCDE*";
void clear()
{
int i;
for(i=0;i<6;i++)
f[i] = ff[i] = 0;
}
void swap(char *t,char *tt)
{
char tmp;
tmp= *t;
*t=*tt;
*tt=tmp;
}
int func(char *p,int n,int m)
{
int i,x,y,ret = 0;
char a[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
if(!strcmp(p,init))
{
return 1;
}
else
{
for(i=0;i<4;i++)
{
x = n + a[i][1];
y = m + a[i][0];
if((x>=0&&x<=1)&&(y>=0&&y<=2)&&(!f[3*n+m]||!ff[3*x+y]))
{
swap(p+3*n+m,p+3*x+y);
f[3*n+m]=1;
ff[3*x+y]=1;
ret = func(p,x,y);
swap(p+2*n+m,p+2*x+y);
if(ret==1)
{
break;
}
}
}
return ret;
}
}
void main()
{
char b[]="ABCDE*";
char c[]="AB*DEC";
char d[]="CAED*B";
char e[]="*ABDEC";
char ee[]="DAB*EC";
printf("%d\n",func(b,1,2));
clear();
printf("%d\n",func(c,0,2));
clear();
printf("%d\n",func(d,1,1));
clear();
printf("%d\n",func(e,0,0));
clear();
printf("%d\n",func(ee,1,0));
