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);
- }