迷宫问题的回溯与递归

今天是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都会遍历到。

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


typedef struct stacknode {
ElemType elem;
struct stacknode* next;
}stacknode, *stack;


InitLinkStack(stack *stack) {
*stack = (stacknode*)malloc(sizeof(stacknode));
stacknode* node = (stacknode*)malloc(sizeof(stacknode));
node = NULL;
(*stack)->next = node;


}
//栈的遍历
TraversalLinkStack(stack stack) {
while (stack->next != NULL) {
printf("(%d %d)<-", (stack->next->elem).x,(stack->next->elem).y);
stack = stack->next;
}
}
//栈反向输出
void InvertedLinkList(stack stack) {
if (stack->next->next) {
InvertedLinkList(stack->next);
}
printf("(%d,%d) ", (stack->next->elem).x, (stack->next->elem).y);
}
//入栈操作
PushLinkStack(stack *stack, ElemType elem) {
stacknode* node = (stacknode*)malloc(sizeof(stacknode));
node->elem = elem;
node->next = (*stack)->next;
(*stack)->next = node;
}
//出栈操作
PopLinkStack(stack *stack) {
//printf("%d ", (*stack)->next->elem);
if ((*stack)->next != NULL) {
(*stack)->next = (*stack)->next->next;
}
}
//取栈顶元素
ElemType getStackTopElem(stack stack) {
return stack->next->elem;
}


void Traial(int a[5][5],ElemType elem,stack* stack) {
int i; ///试探求解下一位置
if (elem.x == last&&elem.y == last) {
InvertedLinkList(*stack);
printf("\n");
}
else {
for (i = 0; i < 4;i++){
if (a[elem.x][elem.y] == 0 && elem.x >= 0 && elem.x <= 4 && elem.y >= 0 && elem.y <= 4) {
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);
}
}
}
}


int main(void) {
int a[5][5] = {
{ 0, 1, 0, 0, 0 },
{ 0, 1, 0, 0, 0 },
{ 0, 1, 0, 0, 0 },
{ 0, 1, 1, 1, 0 },
{ 0, 0, 0, 0, 0 }
};
stack stack;
InitLinkStack(&stack);
Traial(a,firstelem,&stack);
}