對馬踏棋盤的一點研究

2019-11-17 05:47:29

字體：大中小

來源：轉載

供稿：網友

/*對馬踏棋盤的一點研究*/
/* 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--;                      /*退回前一步*/
   }
  }
}
}

上一篇：二級指針

下一篇：對五星紅旗的注釋