题目是这样的:有一个5*5的棋盘,随机的摆放一些棋子,对于任何一颗棋子,如果与他相邻的上下左右的某个方向上存在一颗棋子且这个方向的下一个位置没有棋子,则这颗棋子可跳过与他相邻的棋子,并把与之相邻的棋子“吃掉”,这样一直下去,直到只剩一颗棋子且棋子处于棋盘正中间的位置,就算胜利(即有路可走),否则则说明无路可走。
我的想法是用栈做,每一步的状况将数组转化成一个十进制的数,不停的找,同时使用一个二叉树判断重复。但程序一直调不对,望高手指点~~谢谢啦~~
下面是我编的主程序~~
Move是储存走法的数组,S是存每一步的栈,T是查找二叉树~
main()
{
inta[5][5],Flag,d=0;
ElementTypex1,y1,x2,y2,X,Y,j,i;
ElementTypeX1,Y1,d1;
Stack S;
ElementType Temp;
AvlTree T;
Position P;
T = MakeEmpty( NULL );
Initstack(&S);
Move[0].i=1;
Move[0].j=0;
Move[0].m=2;
Move[0].n=0;
Move[1].i=0;
Move[1].j=1;
Move[1].m=0;
Move[1].n=2;
Move[2].i=-1;
Move[2].j=0;
Move[2].m=-2;
Move[2].n=0;
Move[3].i=0;
Move[3].j=-1;
Move[3].m=0;
Move[3].n=-2;
for(j=0;j<=4;j++)
{
for(i=0;i<=4;i++)
{
if((j==0&&i==2)||(j==1&&i==2))
a[j]=1;
else
a[j]=0;
}
}
X=0;Y=0;
Temp=BinaryToDecimal(a);
push(&S,Temp,X,Y,d);
while(Temp!=4096)
{
while(Temp!=4096&&(X!=4&&Y!=4))
{ Flag=0;
if(a[X][Y]==1)
while(d<4)
{ x1=X+Move[d].i;
y1=Y+Move[d].j;
x2=X+Move[d].m;
y2=Y+Move[d].n;
if(a[x1][y1]==1&&a[x2][y2]==0)
{ a[X][Y]=0;
a[x2][y2]=1;
Temp=BinaryToDecimal(a);
printf("%ld",Temp);
if(Find(Temp,T))
break;
else
{push(&S,Temp,X,Y,d);
T=Insert(Temp,T);
X=0;Y=0;break;Flag=1;
}
}
else
d++;
}
if(Flag!=1)
{ if(Y!=4)
Y++;
else
X++;
}
}
pop(&S,&Temp,&X1,&Y1,&d1);
if(!!StackEmpty(&S))
GetTop(&S,&Temp,&X,&Y,&d);
else
exit("no way!");
}
while(!StackEmpty(&S))
/*输出每一步的走法*/
{ pop(&S,&Temp,&X1,&Y1,&d1);
DecimalToBinary(Temp,a);
Output(a);
}
system("pause");
}
|