ITPub博客

首页 > 应用开发 > IT综合 > 骑士巡游问题 (转)

骑士巡游问题 (转)

原创 IT综合 作者:amyz 时间:2007-11-27 15:10:17 0 删除 编辑
骑士巡游问题 (转)[@more@]

//骑士巡游问题
#include

int f[11][11] ;
int adjm[121][121];
long fgf;
void creatadjm(void);
void e(int,int,int,int);
void travel(int,int);

int n,m;

int main()
{
  int i,j,k,l;
  printf("Input n:");scanf("%d",&n);
  m=n*n;
  creatadjm();
  for(i=1;i<=m;i++)
  {
  for(j=1;j<=m;j++) printf("%2d",adjm[i][j]);
  printf("n");
  }
  getchar();
  printf("Input i,j:");
  scanf("%d %d",&i,&j);
  l=(i-1)*n+j;
  while ((i>0)||(j>0))
  {
  for(i=1;i<=n;i++)
  for(j=1;j<=n;j++)
  f[i][j]=0;
  k=0;

  travel(l,k);
printf("%dn",fgf);fgf=0;

  for(i=1;i<=n;i++)
  {
  for(j=1;j<=n;j++) printf("%4d",f[i][j]);
  printf("n");
  }
  getchar();
  printf("Input i,j:");scanf("%d %d",&i,&j);
  l=(i-1)*n+j;
  }
  return 0;
}

void creatadjm()
{
  int i,j;
  for(i=1;i<=n;i++)
  for(j=1;j<=n;j++)
  f[i][j]=0;
  for(i=1;i<=m;i++)
  for(j=1;j<=m;j++)
  adjm[i][j]=0;

for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(f[i][j]==0)
{
  f[i][j]=1;
  if((i+2<=n)&&(j+1<=n)) e(i,j,i+2,j+1);
  if((i+2<=n)&&(j-1>=1)) e(i,j,i+2,j-1);
  if((i-2>=1)&&(j+1<=n)) e(i,j,i-2,j+1);
  if((i-2>=1)&&(j-1>=1)) e(i,j,i-2,j-1);
  if((j+2<=n)&&(i+1<=n)) e(i,j,i+1,j+2);
  if((j+2<=n)&&(i-1>=1)) e(i,j,i-1,j+2);
  if((j-2>=1)&&(i+1<=n)) e(i,j,i+1,j-2);
  if((j-2>=1)&&(i-1>=1)) e(i,j,i-1,j-2);
}
  return;
}

void travel(int p,int r)
{
  int i,j,q;

  for(i=1;i<=n;i++)
  for(j=1;j<=n;j++)
  if(f[i][j]>r) f[i][j]=0;
  r=r+1;
  i=((p-1)/n)+1;
  j=((p-1)%n)+1;


  f[i][j]=r;

  fgf++;
//if(r==25)printf("%dn",p);
/*
printf("i=%d,j=%d,r=%dn",i,j,r); getchar();
*/

  for(q=1;q<=m;q++)
  {
  i=((q-1)/n)+1;
  j=((q-1)%n)+1;
  if((adjm[p][q]==1)&&(f[i][j]==0)) travel(q,r);
  }
  return;
}

void e(int i1,int j1,int i2,int j2)
{
  adjm[(i1-1)*n+j1][(i2-1)*n+j2]=1;
  adjm[(i2-1)*n+j2][(i1-1)*n+j1]=1;
  return;
}
 

--------------------------------------------------------------------------------
 


来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/10752019/viewspace-985355/,如需转载,请注明出处,否则将追究法律责任。

请登录后发表评论 登录
全部评论
  • 博文量
    3984
  • 访问量
    7335045