对马踏棋盘的一点研究

王朝other·作者佚名  2008-06-01
窄屏简体版  字體: |||超大  

/*对马踏棋盘的一点研究*/

/* QQ:164094487 */

/* Email: fygood@163.com */

/*欢迎与我联系,讨论问题 */

/*本人先后编了两次,第二次进行了改进。改进的思想主要是注重到棋盘上每一点的下一可到达点的个数

(下称为权值)不同,对于可到达点较少(权值小)的点应该先跳上去,这样后来跳的点可跳的方向就比

较多,回溯的现象就比较少,这样就可以大幅度提高速度*/

/*第一次*/

/*原始的马踏棋盘,未加权值,有些点速度很慢*/

#include "stdio.h"

#define N 8

int w=0;

int way1[8]={-2,-1,1,2, 2, 1,-1,-2};

int way2[8]={ 1,2, 2,1,-1,-2,-2,-1};

int ch[N*N]=;

int a[N*N+1][3]=;

int st=1;

char c='y';

void print()

{

int x,y;

printf(" ------%d answer---- ",++w);

for(x=1;x<N+1;x++)

{

printf(" ");

for(y=1;y<N+1;y++)

printf("%2d ",ch[(x-1)*N+y-1]);

printf(" ");

}

printf(" Press n to quit ,press any other key to continue. ");

c=getchar(); /*询问是否继续输出结果*/

}

main()

{

int x,y,way;

printf("Please enter the row and column of the starting point. ");

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 /*此点的八个方向未全走过,应走此方向*/

{

way=a[st][2];

a[st][2]++; /*确定下次应走的方向*/

x=a[st][0]+way1[way];

y=a[st][1]+way2[way]; /*确定按这次的方向走应走到的x,y坐标*/

if(x<1y<1x>Ny>Nch[(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--; /*退回前一步*/

}

}

}

}

/*

第二次:

改进后的马踏棋盘,加入了每点的权值因素,速度极快*/

#include "stdio.h"

#define N 8

int w=0;

int way1[8]={-2,-1,1,2, 2, 1,-1,-2};

int way2[8]={ 1,2, 2,1,-1,-2,-2,-1};

int ch[N*N]=;

int a[N*N+1][3]=;

int dir[N][N][8];

int st=1;

char c='y';

int weight[N][N];

void caculate();

void dirctions();

void print();

int check(int i,int j);

void caculate() /*计算各点的权值*/

{

int i,j,k;

for(i=1;i<=N;i++)

for(j=1;j<=N;j++)

for(k=0;k<N;k++)

{

int x,y;

x=i+way1[k];

y=j+way2[k];

if(x>=1&&x<=N&&y>=1&&y<=N)

weight[i-1][j-1]++;

}

}

int check(int i,int j) /*检查(i,j)是否在棋盘内*/

{

if(i<1i>8j<1j>8)

return 0;

return 1;

}

void directions() /*求出各点的最佳方向序列,即优先向权值小的方向*/

{

int i,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; /*交换两个方向值*/

}

}

}

}

}

void print()

{

int x,y;

printf(" ------%d answer---- ",++w);

for(x=1;x<N+1;x++)

{

printf(" ");

for(y=1;y<N+1;y++)

printf("%2d ",ch[(x-1)*N+y-1]);

printf(" ");

}

printf(" Press n to quit ,press any other key to continue. ");

c=getchar(); /*询问是否继续输出结果*/

}

main()

{

int x,y,way,way0;

caculate();

directions();

printf("Please enter the row and column of the starting point. ");

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(x<1y<1x>Ny>Nch[(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--; /*退回前一步*/

}

}

}

}

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
 
 
© 2005- 王朝網路 版權所有 導航