鱼C论坛

 找回密码
 立即注册
查看: 3064|回复: 0

我用迭代写的马走棋盘,但是一直再找,是不是我写成死循环啦。谁给我说说哪里出问

[复制链接]
发表于 2013-7-6 15:03:05 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #define X 8
  4. #define Y 8

  5. typedef struct step{
  6. int x;
  7. int y;
  8. int door;
  9. } step;

  10. int chessboard[Y][X]; // 建立一个棋盘

  11. step footprint[Y*X+1]; // 记录曾经走过的每一步
  12. int stepNum; // 走过的步数

  13. void push(int x, int y, int door)
  14. {
  15. footprint[stepNum].x = x;
  16. footprint[stepNum].y = y;
  17. footprint[stepNum].door = door;
  18. stepNum++;
  19. }

  20. void pop(int *x, int *y, int *door)
  21. {
  22. stepNum--;
  23. *x = footprint[stepNum].x;
  24. *y = footprint[stepNum].y;
  25. *door = footprint[stepNum].door;
  26. }

  27. int test(int *x, int *y, int door)
  28. {
  29. switch(door)
  30. {
  31. case 0:
  32. if((*x-1)>=0 && (*y-2)>=0 && chessboard[*y-2][*x-1]==0)
  33. {
  34. *x-=1;
  35. *y-=2;
  36. return 1;
  37. }
  38. break;

  39. case 1:
  40. if((*x+1)<X && (*y-2)>=0 && chessboard[*y-2][*x+1]==0)
  41. {
  42. *x+=1;
  43. *y-=2;
  44. return 1;
  45. }
  46. break;

  47. case 2:
  48. if((*x+2)<X && (*y-1)>=0 && chessboard[*y-1][*x+2]==0)
  49. {
  50. *x+=2;
  51. *y-=1;
  52. return 1;
  53. }
  54. break;

  55. case 3:
  56. if((*x+2)<X && (*y+1)<Y && chessboard[*y+1][*x+2]==0)
  57. {
  58. *x+=2;
  59. *y+=1;
  60. return 1;
  61. }
  62. break;

  63. case 4:
  64. if((*x+1)<X && (*y+2)<Y && chessboard[*y+2][*x+1]==0)
  65. {
  66. *x+=1;
  67. *y+=2;
  68. return 1;
  69. }
  70. break;

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

  79. case 6:
  80. if((*x-2)>=0 && (*y+1)<Y && chessboard[*y+1][*x-2]==0)
  81. {
  82. *x-=2;
  83. *y+=1;
  84. return 1;
  85. }
  86. break;

  87. case 7:
  88. if((*x-2)>=0 && (*y-1)>= 0 && chessboard[*y-1][*x-2]==0)
  89. {
  90. *x-=2;
  91. *y-=1;
  92. return 1;
  93. }
  94. break;

  95. default :
  96. break;
  97. }

  98. return 0;
  99. }

  100. void print_chessboard()
  101. {
  102. int i, j;
  103. printf("\n");
  104. for(i = 0; i < Y; i++)
  105. {
  106. for(j = 0; j < X; j++)
  107. {
  108. printf("%02d ",chessboard[i][j]);
  109. }

  110. printf("\n");
  111. }
  112. }

  113. int travel(int x, int y)
  114. {
  115. int i = 0;
  116. int x2, y2;

  117. while(1){
  118. // 建立x y 的副本
  119. x2 = x;
  120. y2 = y;

  121. // 为走过的点写上标号
  122. printf("%d\n", stepNum);
  123. chessboard[y][x] = stepNum + 1;

  124. // 寻找可落脚点

  125. for(; i < 8; i++) // 落脚点只有8个,依次寻找
  126. {
  127. if(test(&x2, &y2, i))
  128. {
  129. if(stepNum == (Y*X-2)) // 如果已将完成 全部点的寻找 则直接打印棋盘 并退出
  130. {
  131. print_chessboard();
  132. return 1;
  133. }

  134. push(x, y, i); // 将走过的点 推入栈中
  135. // 设置 下一个可走点 为当前点
  136. x = x2;
  137. y = y2;
  138. i = 0; // 下一个点 从第一个点开始测试

  139. break; // 找到落脚点 退出循环
  140. }
  141. }

  142. // 所有落脚点均不可落脚,弹出上次落脚点,从上一次落脚点继续寻找

  143. if(i == 8) // 如果i自增到啦8,就是说没有找到下一个落脚点
  144. {
  145. if(stepNum == 0) // 如果没有找到 符合要求的棋盘路径则 返回0
  146. {
  147. return 0;
  148. }

  149. chessboard[y][x] = 0; // 退回时将走错的 归0
  150. pop(&x, &y, &i); // 将上一步弹出 并还原
  151. i++; // 从上一步测试的 下一个点继续测试
  152. }

  153. }
  154. return 0; // 如果没有找到 符合要求的棋盘路径则 返回0
  155. }


  156. int main()
  157. {
  158. if(travel(2, 0) == 0 )
  159. {
  160. printf("没有找到\n");
  161. }
  162. return 0;
  163. }
复制代码
我弄啦快两天,实在是搞不定啦,到底是我机器慢,还是我写成死循环啦?
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

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

本版积分规则

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

GMT+8, 2024-3-29 10:14

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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