#includestdio.h
#defineN8
intw=0;
intway1[8]={-2,-1,1,2,2,1,-1,-2};
intway2[8]={1,2,2,1,-1,-2,-2,-1};
intch[N*N]={0};
inta[N*N+1][3]={0};
intdir[N][N][8];
intst=1;
charc=y;
intweight[N][N];
voidcaculate();
voiddirctions();
voidprint();
intcheck(inti,intj);
voidcaculate()/*计算各点的权值*/
{
inti,j,k;
for(i=1;i<=N;i++)
for(j=1;j<=N;j++)
for(k=0;k<N;k++)
{
intx,y;
x=i+way1[k];
y=j+way2[k];
if(x>=1&&x=1&&y<=N)
weight[i-1][j-1]++;
}
}
intcheck(inti,intj)/*检查(i,j)是否在棋盘内*/
{
if(i8||j8)
return0;
return1;
}
voiddirections()/*求出各点的最佳方向序列，即优先向权值小的方向*/
{
inti,j,k,m,n1,n2,x1,y1,x2,y2,way_1,way_2;
for(i=0;i<N;i++)
for(j=0;j<N;j++)
{
for(k=0;k<8;k++)
dir[i][j][k]=k;
for(k=0;k<8;k++)
{
for(m=k+1;m<8;m++)/*对每个方向考察看有没有更好的*/
{
way_1=dir[i][j][k];
x1=i+way1[way_1];
y1=j+way2[way_1];
way_2=dir[i][j][m];
x2=i+way1[way_2];
y2=j+way2[way_2];
n1=check(x1+1,y1+1);
n2=check(x2+1,y2+1);
if(
(n1==0&&n2)||/*k方向不可达到，而m方向可达到*/
(n1&&n2&&weight[x1][y1]>weight[x2][y2])/*都可达到但m方向权值小*/
)
{
dir[i][j][k]=way_2;
dir[i][j][m]=way_1;/*交换两个方向值*/
}
}
}
}
}
voidprint()
{
intx,y;
printf(\n------%danswer----\n,++w);
for(x=1;x<N+1;x++)
{
printf(\n);
for(y=1;y<N+1;y++)
printf(%2d,ch[(x-1)*N+y-1]);
printf(\n);
}
printf(\nPressntoquit,pressanyotherkeytocontinue.\n);
c=getchar();/*询问是否继续输出结果*/
}
main()
{
intx,y,way,way0;
caculate();
directions();
printf(Pleaseentertherowandcolumnofthestartingpoint.\n);
scanf(%d,%d,&a[1][0],&a[1][1]);/*输入行数和列数*/
getchar();/*接收回车符*/
x=a[1][0],y=a[1][1];
ch[(x-1)*N+y-1]=1;/*在ch数组中对相应点赋值*/
while(1)
{
if(a[1][2]>=8)/*出发点的八个方向都已走过，表示所有的方法均已找出*/
break;
if(a[st][2]>=8)/*此点的八个方向都已走过，应该退回到上一次走的点*/
{
x=a[st][0];
y=a[st][1];
ch[(x-1)*N+y-1]=0;/*将这一点被走过的痕迹抹去*/
a[st][0]=a[st][1]=a[st][2]=0;
a[st-1][2]++;/*使上一次走的点走的方向发生变化*/
st--;/*步数减一*/
}
else/*此点的八个方向未全走过，应走此方向*/
{
way0=a[st][2];
a[st][2]++;/*确定下次应走的方向*/
x=a[st][0];
y=a[st][1];
way=dir[x-1][y-1][way0];
x=a[st][0]+way1[way];
y=a[st][1]+way2[way];/*确定按这次的方向走应走到的x,y坐标*/
if(xN||y>N||ch[(x-1)*N+y-1]!=0)/*此点不满足要求*/
continue;
ch[(x-1)*N+y-1]=++st;/*走到这一点*/
a[st][0]=x;
a[st][1]=y;
a[st][2]=0;/*标记这一步*/
if(st==N*N)/*步数已满*/
{
print();/*输出结果*/
if(c==n)
break;
ch[(x-1)*N+y-1]=0;
a[st][0]=a[st][1]=a[st][2]=0;
a[st-1][2]++;
st--;/*退回前一步*/
}
}
}
}
