求解！！2012蓝桥杯高职C试题 第十题
10. 移动字母
2x3=6个方格中放入ABCDE五个字母，右下角的那个格空着。如图1所示。
和空格子相邻的格子中的字母可以移动到空格中，比如，图中的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
[解决办法]
2x3=6个方格中放入ABCDE五个字母，右下角的那个格空着。如图1所示。
在格子中移动字母
____________________
| | | |
|__A__|__B__|__C___|
……
向四个方向递归
#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));
}
这是别人解决的方法
