鱼C论坛

 找回密码
 立即注册
查看: 4041|回复: 3

求帮忙看看马踏棋盘算法哪里错了。

[复制链接]
发表于 2017-1-26 12:15:46 | 显示全部楼层 |阅读模式
10鱼币
本帖最后由 gascd 于 2017-1-26 12:26 编辑

代码和小甲鱼的对照了,除了nextxy()函数以外,其他的函数都差不多。然而我的nextxy()函数就算不出解来,而小甲鱼的nextxy()函数就能够算出来。
如下为代码:
  1. #include <stdio.h>
  2. #include <time.h>
  3. #include <stdlib.h>

  4. #define X 8
  5. #define Y 8

  6. int chess[X][Y];

  7. #if 0
  8. //小甲鱼的正确的代码
  9. int nextxy(int *x, int *y, int count)
  10. {
  11.         switch(count)
  12.         {
  13.                 case 0:
  14.                         if( *x+2<=X-1 && *y-1>=0 && chess[*x+2][*y-1]==0 )
  15.                         {
  16.                                 *x = *x + 2;
  17.                                 *y = *y - 1;
  18.                                 return 1;
  19.                         }
  20.                         break;

  21.                 case 1:
  22.                         if( *x+2<=X-1 && *y+1<=Y-1 && chess[*x+2][*y+1]==0 )
  23.                         {
  24.                                 *x = *x + 2;
  25.                                 *y = *y + 1;
  26.                                 return 1;
  27.                         }
  28.                         break;

  29.                 case 2:
  30.                         if( *x+1<=X-1 && *y-2>=0 && chess[*x+1][*y-2]==0 )
  31.                         {
  32.                                 *x = *x + 1;
  33.                                 *y = *y - 2;
  34.                                 return 1;
  35.                         }
  36.                         break;

  37.                 case 3:
  38.                         if( *x+1<=X-1 && *y+2<=Y-1 && chess[*x+1][*y+2]==0 )
  39.                         {
  40.                                 *x = *x + 1;
  41.                                 *y = *y + 2;
  42.                                 return 1;
  43.                         }
  44.                         break;

  45.                 case 4:
  46.                         if( *x-2>=0 && *y-1>=0 && chess[*x-2][*y-1]==0 )
  47.                         {
  48.                                 *x = *x - 2;
  49.                                 *y = *y - 1;
  50.                                 return 1;
  51.                         }
  52.                         break;

  53.                 case 5:
  54.                         if( *x-2>=0 && *y+1<=Y-1 && chess[*x-2][*y+1]==0 )
  55.                         {
  56.                                 *x = *x - 2;
  57.                                 *y = *y + 1;
  58.                                 return 1;
  59.                         }
  60.                         break;

  61.                 case 6:
  62.                         if( *x-1>=0 && *y-2>=0 && chess[*x-1][*y-2]==0 )
  63.                         {
  64.                                 *x = *x - 1;
  65.                                 *y = *y - 2;
  66.                                 return 1;
  67.                         }
  68.                         break;

  69.                 case 7:
  70.                         if( *x-1>=0 && *y+2<=Y-1 && chess[*x-1][*y+2]==0 )
  71.                         {
  72.                                 *x = *x - 1;
  73.                                 *y = *y + 2;
  74.                                 return 1;
  75.                         }
  76.                         break;

  77.                 default:
  78.                         break;
  79.         }

  80.         return 0;
  81. }
  82. #endif

  83. #if 1
  84. //我的错误代码
  85. // 判断下一步能不能走
  86. int nextxy(int *x, int *y, int count)
  87. {
  88.         switch(count)
  89.         {
  90.         case 0:if((*x)-1>=0 && (*y)+2<=Y-1 && chess[*x-1][*y+2]==0)
  91.                    {
  92.                            *x = (*x)-1;
  93.                            *y = (*y)+2;
  94.                            return 1;
  95.                    } break;
  96.         case 1:if((*x)+1<=X-1 && (*y)+2<=Y-1 && chess[*x+1][*y+2]==0)
  97.                         {
  98.                                 *x = (*x)+1;
  99.                                 *y = (*y)+2;
  100.                                 return 1;
  101.                    } break;
  102.         case 2:if((*x)+2<=X-1 && (*y)+1<=Y-1 && chess[*x+2][*y+1]==0)
  103.                    {
  104.                            *x = (*x)+2;
  105.                            *y = (*y)+1;
  106.                            return 1;
  107.                    }break;
  108.         case 3:if((*x)+2<=X-1 && (*y)-1>=0 && chess[*x+2][*y-1]==0)
  109.                         {
  110.                                 *x = (*x)+2;
  111.                                 *y = (*y)-1;
  112.                                 return 1;
  113.                    } break;
  114.         case 4:if((*x)+1<=X-1 && (*y)-2>=0 && chess[*x+1][*y-2]==0)
  115.                    {   
  116.                            *x = (*x)+1;
  117.                            *y = (*y)-2;
  118.                            return 1;
  119.                    } break;
  120.         case 5:if((*x)-1>=0 && (*y)-2>=0 && chess[*x-1][*y-2]==0)
  121.                    {   
  122.                            *x = (*x)-1;
  123.                            *y = (*y)-2;
  124.                            return 1;
  125.                    } break;
  126.         case 6:if((*x)-2>=0 && (*y)-1>=0 && chess[*x-2][*y-1]==0)
  127.                    {   
  128.                            *x = (*x)-2;
  129.                            *y = (*y)-1;
  130.                            return 1;
  131.                    } break;
  132.         case 7:if((*x)-2>=0 && (*y)+1<=Y-1 && chess[*x-2][*y+1]==0)
  133.                         {   
  134.                                 *x = (*x)-2;
  135.                                 *y = (*y)+1;
  136.                                 return 1;
  137.                    } break;
  138.         default:break;
  139.         }
  140.         return 0;
  141. }
  142. #endif


  143. void print()
  144. {
  145.         int i, j;
  146.         for(i=0; i<X; i++)
  147.         {
  148.                 for(j=0; j<Y; j++)
  149.                 {
  150.                         printf("%2d\t", chess[i][j]);
  151.                 }
  152.                 printf("\n");
  153.         }
  154. }

  155. //深度优先遍历
  156. //(x,y)为位置坐标
  157. //tag是标识变量,每走一步tag+1
  158. int TravelChessBoard(int x, int y, int tag)
  159. {
  160.         int x1, y1, flag, count;
  161.         x1 = x;
  162.         y1 = y;
  163.         flag = count = 0;
  164.         chess[x][y] = tag;

  165.         //判断是否走完
  166.         if(X*Y == tag)
  167.         {
  168.                 print();
  169.                 return 1;
  170.         }
  171.         //判断下一步能不能走,能flag = 1
  172.         flag = nextxy(&x1, &y1, count);
  173.         while(0 == flag && count < 8)
  174.         {
  175.                 count++;
  176.                 flag = nextxy(&x1, &y1, count);
  177.         }

  178.         while(flag)
  179.         {
  180.                 if(TravelChessBoard(x1, y1, tag+1))
  181.                         return 1;

  182.                 //没找到下一个可以跳的,则回溯
  183.                 x1 = x;
  184.                 y1 = y;
  185.                 count++;
  186.                 flag = nextxy(&x1, &y1, count);
  187.                 while(0 == flag && count < 8)
  188.                 {
  189.                         count++;
  190.                         flag = nextxy(&x1, &y1, count);
  191.                 }
  192.         }
  193.         //这条路不通,还原标志
  194.         if(0 == flag)
  195.                 chess[x1][y1] = 0;
  196.         return 0;
  197. }

  198. int main()
  199. {
  200.         int i, j;
  201.         clock_t start, finish;

  202.         start = clock();
  203.         for(i=0; i<X; i++)
  204.         {
  205.                 for(j=0; j<Y; j++)
  206.                 {
  207.                         chess[i][j]=0;
  208.                 }
  209.         }
  210.         if(!TravelChessBoard(2, 0, 1))
  211.                 printf("\nsorry,马踏棋盘失败!\n");
  212.         finish = clock();
  213.         printf("\n本次计算时间为%lf秒\n",(double)(finish-start)/CLOCKS_PER_SEC);
  214.        
  215.         system("pause");
  216.         return 0;
  217. }

复制代码

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2017-1-28 21:54:08 | 显示全部楼层
不是哪里错了,而是我的nextxy()函数里,case的顺序不同,导致了算法的时间大大大大大大的增加。大约需要一个多月算出来!!!!!!!!
咳咳,其实只要换个简单的点,就可以了,或者改一下case顺序。
总之,错的人不是我,错的是……这个时间太长了。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2018-2-18 22:50:54 | 显示全部楼层
gascd 发表于 2017-1-28 21:54
不是哪里错了,而是我的nextxy()函数里,case的顺序不同,导致了算法的时间大大大大大大的增加。大约需要一 ...

我的也是,不知道为啥nextxy顺序不对就会出错呢,这是什么原理,求大神解答
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2018-3-18 00:57:29 | 显示全部楼层
Code_mzh 发表于 2018-2-18 22:50
我的也是,不知道为啥nextxy顺序不对就会出错呢,这是什么原理,求大神解答

这个我搞懂了。因为nextxy顺序不对,所以马儿还在一步一步的试着跳。直到把正确的路径给找出来。这个过程需要很长的时间。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 23:55

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表