迷宫问题的回溯与递归

2080阅读 0评论2015-09-19 九阳神功爱喝茶
分类:C/C++

今天是2015年九月十九号,刚才因为要写八皇后问题,因此又把前段时间写的迷宫问题拿在一起做了个对比,发现之前有些地方写的不好,所以又给重构了一下。以下心得作为备忘:
1)以前是已知第i次满足条件,暴力递归探究第i+1次的情况,如果满足,再探讨i+2的情况,这种情况下很容易遗漏i=0时候,因为是直接探讨i+1的情况,没有探讨第i的情况。现在直接假设前i-1次满足情况,探讨第i次的情况,这样就统一了。
2)注意递归不满足条件时候要注意恢复原来的值
if (a[elem.x][elem.y] == 0 && elem.x >= 0 && elem.x <= 4 && elem.y >= 0 && elem.y <= 4) {
橘色表示探讨第i次满足的情况下,修改第i个的参数值,然后再探讨i+1次的情况。
如果第i+1次的探讨出错,则要恢复第i的参数。
a[elem.x][elem.y] = 2;
PushLinkStack(stack, elem);
elem.x = elem.x + xShift[i];
elem.y = elem.y + yShift[i];
Traial(a,elem, stack);
elem.x = elem.x - xShift[i];
elem.y = elem.y - yShift[i];
a[elem.x][elem.y] = 0;
PopLinkStack(stack);
3)其实我在思考,如果是从第一行的任意一个位置出发,那是不是也意味着每次只用传递一个参数i即可,因为会所有的j都会遍历到。

点击(此处)折叠或打开

  1. #pragma warning(disable:4996)
  2. #include<stdio.h>
  3. #include<stdlib.h>
  4. typedef struct {
  5. int x;//横坐标
  6. int y;//纵坐标
  7. }ElemType;
  8. ElemType firstelem = { 0,};
  9. int xShift[4] = { 0,0,-1,}; //相邻位置相对于当前位置的x坐标 
  10. int yShift[4] = { -1,1,0,}; //相邻位置相对于当前位置的y坐标 
  11. int last= 4;


  12. typedef struct stacknode {
  13. ElemType elem;
  14. struct stacknode* next;
  15. }stacknode, *stack;


  16. InitLinkStack(stack *stack) {
  17. *stack = (stacknode*)malloc(sizeof(stacknode));
  18. stacknode* node = (stacknode*)malloc(sizeof(stacknode));
  19. node = NULL;
  20. (*stack)->next = node;


  21. }
  22. //栈的遍历
  23. TraversalLinkStack(stack stack) {
  24. while (stack->next != NULL) {
  25. printf("(%d %d)<-", (stack->next->elem).x,(stack->next->elem).y);
  26. stack = stack->next;
  27. }
  28. }
  29. //栈反向输出
  30. void InvertedLinkList(stack stack) {
  31. if (stack->next->next) {
  32. InvertedLinkList(stack->next);
  33. }
  34. printf("(%d,%d) ", (stack->next->elem).x, (stack->next->elem).y);
  35. }
  36. //入栈操作
  37. PushLinkStack(stack *stack, ElemType elem) {
  38. stacknode* node = (stacknode*)malloc(sizeof(stacknode));
  39. node->elem = elem;
  40. node->next = (*stack)->next;
  41. (*stack)->next = node;
  42. }
  43. //出栈操作
  44. PopLinkStack(stack *stack) {
  45. //printf("%d ", (*stack)->next->elem);
  46. if ((*stack)->next != NULL) {
  47. (*stack)->next = (*stack)->next->next;
  48. }
  49. }
  50. //取栈顶元素
  51. ElemType getStackTopElem(stack stack) {
  52. return stack->next->elem;
  53. }


  54. void Traial(int a[5][5],ElemType elem,stack* stack) {
  55. int i; ///试探求解下一位置 
  56. if (elem.== last&&elem.== last) {
  57. InvertedLinkList(*stack);
  58. printf("\n");
  59. }
  60. else {
  61. for (= 0; i < 4;i++){
  62. if (a[elem.x][elem.y] == 0 && elem.>= 0 && elem.<= 4 && elem.>= 0 && elem.<= 4) {
  63. a[elem.x][elem.y] = 2;
  64. PushLinkStack(stack, elem);
  65. elem.= elem.+ xShift[i];
  66. elem.= elem.+ yShift[i];
  67. Traial(a,elem, stack);
  68. elem.= elem.- xShift[i];
  69. elem.= elem.- yShift[i];
  70. a[elem.x][elem.y] = 0;
  71. PopLinkStack(stack);
  72. }
  73. } 
  74. }
  75. }


  76. int main(void) {
  77. int a[5][5] = {
  78. { 0, 1, 0, 0, 0 },
  79. { 0, 1, 0, 0, 0 },
  80. { 0, 1, 0, 0, 0 },
  81. { 0, 1, 1, 1, 0 },
  82. { 0, 0, 0, 0, 0 }
  83. };
  84. stack stack;
  85. InitLinkStack(&stack);
  86. Traial(a,firstelem,&stack);
  87. }

上一篇:八皇后问题的递归实现
下一篇:链栈的基本操作API