Code666 (代码贴、代码片段)

[C] 骑士走棋盘算法 →→→→→进入此内容的聊天室

来自 , 2020-01-17, 写在 C, 查看 161 次.
URL http://www.code666.cn/view/9f44e956
  1. #include<stdio.h>
  2.  
  3. /*骑士走棋盘算法，骑士的走法为西洋棋的走法，骑士可以由任一个位置出发，它要如何走完[所有的位置？*/
  4.  
  5. /*解法骑士的走法，基本上可以使用递回来解决，但是纯綷的递回在维度大时相当没有效率，一个聪明的解法由J.C.Warnsdorff在1823年提出，简单的说，先将最难的位置走完，接下来的路就宽广了，骑士所要走的下一步，「为下一步再选择时，所能走的步数最少的一步」，使用这个方法，在不使用递回的情况下，可以有较高的机率找出走法（找不到走法的机会也是有的）*/
  6.  
  7.  
  8. int board[8][8]={0};
  9. int travel(int x,int y);
  10.  
  11. int main ( void )
  12. {
  13.         int startx,starty;
  14.         int i,j;
  15.         printf ( "输入起始点：" );
  16.         scanf ( "%d%d",&startx,&starty );
  17.  
  18.         if ( travel(startx,starty) )
  19.         {
  20.                 printf ( "游历完成！\n" );
  21.         }
  22.         else
  23.         {
  24.                 printf ( "游历失败！\n" );
  25.         }
  26.  
  27.         for ( i=0; i<8; i++ )
  28.         {
  29.                 for ( j=0; j<8; j++ )
  30.                 {
  31.  
  32.  
  33.                         printf ( "%2d",board[i][j] );
  34.                 }
  35.                 putchar ( '\n' );
  36.         }
  37.         return 0;
  38. }
  39.  
  40. int travel ( int x,int y )
  41. {
  42.         // 对应骑士可走的八个方向
  43.         int ktmove1[8]={-2,-1,1,2,2,1,-1,-2};
  44.         int ktmove2[8]={1,2,2,1,-1,-2,-2,-1};
  45.  
  46.         // 测试下一步的出路
  47.         int nexti[8]={0};
  48.         int nextj[8]={0};
  49.         // 记录出路的个数
  50.         int exists[8]={0};
  51.         int i,j,k,m,l;
  52.         int tmpi,tmpj;
  53.         int count,min,tmp;
  54.  
  55.         i=x;
  56.         j=y;
  57.         board[i][j]=1;
  58.  
  59.         for ( m=2; m<=64; m++ )
  60.         {
  61.                 for ( l=0; l<8; l++ )
  62.                         exists[l]=0;
  63.  
  64.                 l=0;
  65.  
  66.                 // 试探八个方向
  67.                 for ( k=0; k<8; k++ )
  68.                 {
  69.                         tmpi=i+ktmove1[k];
  70.                         tmpj=j+ktmove2[k];
  71.  
  72.                         // 如果是边界了，不可走
  73.                         if ( tmpi<0||tmpj<0||tmpi>7||tmpj>7 )
  74.                                 continue;
  75.  
  76.                         // 如果这个方向可走，记录下来
  77.  
  78.  
  79.                         if ( board[tmpi][tmpj]==0 )
  80.                         {
  81.                                 nexti[l]=tmpi;
  82.                                 nextj[l]=tmpj;
  83.                                 // 可走的方向加一个
  84.                                 l++;
  85.                         }
  86.                 }
  87.  
  88.                 count=l;
  89. // 如果可走的方向为0个，返回
  90.                 if ( count==0 )
  91.                 {
  92.                         return 0;
  93.                 }
  94.                 else if ( count==1 )
  95.                 {
  96.                         // 只有一个可走的方向
  97.                         // 所以直接是最少出路的方向
  98.                         min=0;
  99.                 }
  100.                 else
  101.                 {
  102.                         // 找出下一个位置的出路数
  103.                         for ( l=0; l<count; l++ )
  104.                         {
  105.                                 for ( k=0; k<8; k++ )
  106.                                 {
  107.                                         tmpi=nexti[l]+ktmove1[k];
  108.                                         tmpj=nextj[l]+ktmove2[k];
  109.                                         if ( tmpi<0||tmpj<0||
  110.                                                 tmpi>7||tmpj>7 )
  111.                                         {
  112.                                                 continue;
  113.                                         }
  114.                                         if ( board[tmpi][tmpj]==0 )
  115.                                                 exists[l]++;
  116.                                 }
  117.                         }
  118.                         tmp=exists[0];
  119.                         min=0;
  120.                         // 从可走的方向中寻找最少出路的方向
  121.                         for ( l=1; l<count; l++ )
  122.                         {
  123.                                 if ( exists[l]<tmp )
  124.                                 {
  125.                                         tmp=exists[l];
  126.                                         min=l;
  127.                                 }
  128.                         }
  129.  
  130.  
  131.                 }
  132.  
  133.                 // 走最少出路的方向
  134.                 i=nexti[min];
  135.                 j=nextj[min];
  136.                 board[i][j]=m;
  137.         }
  138.  
  139.         return 1;
  140. }

回复 "骑士走棋盘算法"

这儿你可以回复上面这条便签

captcha

贴代码片段 - Code666