数据结构02 栈的迷宫求解问题实现
约定：
通过数组形式表示迷宫。
用1表示不通，0表示通路。
方向变量：1表示东，2表示南，3表示西，4表示北。
将入口坐标作为当前位置，按顺时针探索入口的四个附近方向值。
如果当前位置值为0：
如果附近的其中一个方向值为0，表示可以通过，则方向变量为该方向代表的值。将当前位置的值改为2表示已经经过。将当前位置压栈，将当前位置移动到可以通过的位置。具体通过横纵坐标的加减一来实现。如果附近四个方向中没0，则将该位置值变为1。退至原位置。具体也是通过横纵坐标的加减来实现，即如果当前方向为1，则纵坐标减1。
如果当前位置值为2:
首先判断四个方向是否有值为0，若有，直接跳转到值为0的位置。并修改方向值。若没有，退栈，说明此路不通，以相反方向退回一位。
如果当前位置与终点位置相同，退出循环。
循环条件为栈是否为空，若空，说明从起点又退回到了起点，没有可以通过的路径。若非空，以栈底到栈顶的顺序输出位置。
1 #include <stdio.h>
2 #include <cstdlib>
3 #include <string.h>
4
5 #define STACK_INIT_SIZE 100
6 #define STACKINCREMENT 10
7
8 typedef struct {
9 int x; //x axis
10 int y; //y axis
11 int z; //表示是否走过
12 int di;//方向
13 }Pos1;
14
15
16 typedef struct {
17 Pos1 *base;
18 Pos1 *top;
19 int stacksize;
20 }SqStack;
21 int StackEmpty(SqStack &S)
22 {
23 if (S.top == S.base)
24 return 1;
25 else return 0;
26 }
27 int Init(SqStack &S)
28 {
29 S.base = (Pos1 *)malloc(STACK_INIT_SIZE *sizeof(int));
30 if (!S.base) return 0;
31 S.top = S.base;
32 S.stacksize = STACK_INIT_SIZE;
33 return 1;
34 }//Init
35
36 int Push(SqStack &S,Pos1 e)
37 {
38 if(S.top - S.base >= S.stacksize){
39 S.base = (Pos1 *)realloc(S.base,(S.stacksize + STACKINCREMENT)*sizeof(int));
40 if(!S.base) return 0;
41 S.top = S.base + S.stacksize;
42 S.stacksize += STACKINCREMENT;
43 }//if
44 *S.top = e;
45 S.top++;
46 return 1;
47 }//Push
48
49 int Pop(SqStack &S)
50 {
51 if (S.top == S.base) return 0;
52 --S.top;
53 return 1;
54 }
55
56 int getTop(SqStack S,Pos1 &cur)
57 {
58 cur = *(S.top - 1);
59 return 0;
60 }
关键是对于题目实现的具体步骤理解清楚，从以顺时针判断四个方向，进而想到将方向值用1，2，3，4来表示。因为要判断四个方向的值，又有走过的路和能走的路的冲突，因为可以将走过的路值设为2。每通过一个值为0的位置压栈，但是若为死路则不必。退栈通过反向前进来实现。退栈的条件是当前位置已经经过而且四个方向没有可以前进的路。
迷宫求解是用穷举法来实现的。