题目描述
2×3=6个方格中放入ABCDE五个字母,右下角的那个格空着。
和空格子相邻的格子中的字母可以移动到空格中,比如,图中的C和E就可以移动,移动后的局面分别是:
A B
D E C
A B C
D E
为了表示方便,我们把6个格子中字母配置用一个串表示出来,比如上边的两种局面分别表示为:
AB*DEC
ABCD*E
题目的要求是:请编写程序,由用户输入若干表示局面的串,程序通过计算,输出是否能通过对初始状态经过若干次移动到达该状态。可以实现输出1,否则输出0。初始状态为:ABCDE*
输入
先是一个整数n,表示接下来有n行状态。
输出
程序输出也应该是n行1或0
样例输入
3
ABCDE*
AB*DEC
CAED*B
样例输出
1
1
0
参考代码
#include<stdio.h>
#include<string.h>
char a[10];
char b[750][7];
char c[6]={'A','B','C','D','E','*'};
int t[4][2]={1,0,0,1,0,-1,-1,0};
int temp;
int fun()
{
int i,j,x,y,q,front=0,rear,newx,newy,newz,z;
char v[10],u[10];
memset(b,0,sizeof(b));
strcpy(b[front],a);
rear=1;
while(front<rear)
{
strcpy(u,b[front]);
if(!(strcmp(u,c))) return 1; else
{
for (z=0;z<6;z++)
if(u[z]=='*') break;
x=z/3;
y=z%3;
for (i=0;i<4;i++)
{
newx=x+t[i][0];
newy=y+t[i][1];
newz=newx*3+newy;
strcpy(v,u);
if(newx>=0&&newx<2&&newy>=0&&newy<3)
{
v[z]=u[newz];
v[newz]=u[z];
q=1;
for (j=0;j<rear;j++)
if(!strcmp(v,b[j]))
{
q=0;
break;
}
if(q)
strcpy(b[++rear],v);
}
}
}
front++;
}
return 0;
}
int main()
{
int k;
scanf("%d",&k);
while(k--)
{
temp=1;
scanf("%s",a);
printf("%dn",fun());
}
return 0;
}
解析
暂无