关于马踏棋盘算法的一些感悟与大家分享一下:
首先明确思路:从一个坐标出发,从下一步八中走法选择一种,走到底,当此路不通时,才回到上一步,走其他方法。
简单点说就是,路通一直走下去,路不通回溯上一步。。understanding!!!!!
还有说一下上面楼主代码的一点小错误,,,变量count<7,这点我不是很认同,我觉得应该改为count<=7吧!!
说到这里我附上代码(代码中X,Y定义为5,方便计算机计算,当然如果你的计算机配置不错,,可以把X ,Y的值定义为8 )#include<cstdio>
#include<ctime>
#define X 5
#define Y 5
int chess[X][Y]={0};
void printChess(){
printf("This is horse Chess:\n");
for(int i=0;i<X;i++){
for(int j=0;j<Y;j++){
printf("%2d ",chess[i][j]);
}
printf("\n");
}
}
int next(int *x,int *y,int step){
switch(step)
{
case 0:
if(*y+2<=Y-1 && *x-1>=0 && chess[*x-1][*y+2]==0)
{
*y+=2;
*x-=1;
return 1;
}
break;
case 1:
if(*y+2<=Y-1 && *x+1<=X-1 && chess[*x+1][*y+2]==0)
{
*y+=2;
*x+=1;
return 1;
}
break;
case 2:
if(*y+1<=Y-1 && *x+2<=X-1 && chess[*x+2][*y+1]==0)
{
*y+=1;
*x+=2;
return 1;
}
break;
case 3:
if(*y-1>=0 && *x+2<=X-1 && chess[*x+2][*y-1]==0)
{
*y-=1;
*x+=2;
return 1;
}
break;
case 4:
if(*y-2>=0 && *x+1<=X-1 && chess[*x+1][*y-2]==0)
{
*y-=2;
*x+=1;
return 1;
}
break;
case 5:
if(*y-2>=0 && *x-1>=0 && chess[*x-1][*y-2]==0)
{
*y-=2;
*x-=1;
return 1;
}
break;
case 6:
if(*y-1>=0 && *x-2>=0 && chess[*x-2][*y-1]==0)
{
*y-=1;
*x-=2;
return 1;
}
break;
case 7:
if(*y+1<=Y-1 && *x-2>=0 && chess[*x-2][*y+1]==0)
{
*y+=1;
*x-=2;
return 1;
}
break;
default:
break;
}
return 0;
}
int horse(int x,int y,int tag){
int x_t=x,y_t=y;
int flag=0,count=0;
chess[x][y]=tag;
if(tag==X*Y){
printChess();
return 1;
}
flag=next(&x_t,&y_t,count);
while(!flag && count<=7){
count++;
flag=next(&x_t,&y_t,count);
}
while(flag){
if(horse(x_t,y_t,tag+1))
return 1;
x_t=x,y_t=y,count++;
flag=next(&x_t,&y_t,count);
while(!flag && count<=7){
count++;
flag=next(&x_t,&y_t,count);
}
}
if(!flag)chess[x][y]=0;
return 0;
}
int main()
{
clock_t begin,end;
begin=clock();
if(!horse(2,0,1)){
printf("The horse Chess is unavailable!");
}
end=clock();
printf("This time used is %lf\n",(double)(end-begin)/CLOCKS_PER_SEC);
return 0;
}
特别说明:因为代码没有加注释,在明白思路的前提下看才会更省力哦。。 |