来源：https://software.intel.com/zh-cn/blogs/2014/03/03/?utm_campaign=CSDN&utm_source=intel.csdn.net&utm_medium=Link&utm_content=%20others-%20suanfa
注：为了不离开本节讨论的重点--栈，迷宫的自动生成以后重新写。这里用简单的二维数组代替，手动迷宫，呵呵！
MAP里面0代表墙（通不过），1代表空格（可通过）代码中每一步有详细注释。欢迎大家交流，嘻嘻。
1 // DataStructure_ZJC.cpp : 定义控制台应用程序的入口点。 2 /* 3 二. 栈的应用-迷宫解题 4 */ 5 #include "stdafx.h" 6 #include<stdio.h> 7 #include<malloc.h> 8 #include<stdlib.h> 9 10 #define TRUE 1 11 #define FALSE 0 12 #define OK 1 13 #define ERROR 0 14 #define INFEASIBLE -1 15 #define OVERFLOW -2 16 17 typedef struct 18 { 19 int x; //x坐标 20 int y; //y坐标 21 }Postype; //坐标类型 22 typedef struct 23 { 24 //int ord; //通道块在路径上的序号 25 //Postype seat; //通道块在迷宫中的坐标 26 //int di; //从此通道块走向下一通道块的“方向” 27 int x; 28 int y; //元素坐标 29 30 // bool track; //是否已经走过 31 }ElemType; //栈的元素类型 32 33 int MAP[9][9] = /*二维数组就够用了，先从简单的地图开始*/ 34 { 35 //0 1 2 3 4 5 6 7 8 36 37 0,0,0,0,0,0,0,0,0, 38 0,1,0,0,1,1,1,1,0, 39 0,1,0,0,1,1,1,1,0, 40 0,1,1,1,1,0,1,1,0, 41 0,1,0,1,0,1,1,1,0, 42 0,1,0,1,0,1,1,1,0, 43 0,1,0,1,0,1,1,1,0, 44 0,0,0,1,1,1,1,1,0, 45 0,0,0,0,0,0,0,0,0, 46 47 48 }; 49 /*-------------------------------------栈的元素类型定义完毕-------------------------*/ 50 typedef int Status; //函数返回值 51 52 #define STACK_INIT_SIZE 100 // 栈的初始大小 53 #define STACK_INCREMENT 10 // 每次增加的空间大小 54 55 56 //下面给出栈的相关定义 57 typedef struct 58 { 59 ElemType *base; //在构造栈之前和销毁之后，base的值为NULL 60 ElemType *top; //栈顶指针 61 int stacksize; //当前已分配的存储空间，以元素为单位 62 }ZJC_Stack; 63 64 //--------------------------------------栈基本操作的算法部分-------------------------- 65 //栈的初始化 66 Status InitStack(ZJC_Stack &S) 67 { 68 69 S.base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType)); //分配内存空间 70 if(!S.base) 71 exit(OVERFLOW); 72 73 else //否则分配成功 74 { 75 S.top = S.base; 76 S.stacksize = STACK_INIT_SIZE; 77 return OK; 78 } 79 80 } 81 //获得栈顶元素 82 ElemType GetTop(ZJC_Stack S) 83 { 84 if(S.top == S.base ) 85 exit(ERROR); 86 return *(S.top - 1); 87 } 88 //压栈 89 Status Push(ZJC_Stack &S,ElemType e) 90 { 91 if(S.top - S.base >= S.stacksize) 92 { 93 S.base = (ElemType*)realloc(S.base,(S.stacksize + STACK_INCREMENT) * sizeof(ElemType)); 94 if(!S.base) 95 exit(OVERFLOW); 96 S.stacksize += STACK_INCREMENT; 97 S.top = S.base + S.stacksize; 98 } 99 *S.top++ = e; 100 return OK; 101 } 102 void Print_Path(ZJC_Stack S) //打印出栈中的元素 103 { 104 printf(" 寻路完成..路径坐标值如下：...... "); 105 ElemType *p = S.base; //首先p指向栈底指针 106 ElemType temp; 107 while( p != S.top) //只要没有到顶端，指针就移动，然后输出元素值 108 { 109 temp = *p; 110 printf(" 路径 x = %d , y = %d",temp.x,temp.y); 111 p++; 112 } 113 } 114 115 //出栈函数 116 Status Pop(ZJC_Stack &S,ElemType &e) 117 { 118 if(S.top == S.base ) //空栈，返回错误 119 return ERROR; 120 else //不是空栈 121 { 122 e = * --S.top; 123 return OK; 124 } 125 } 126 void PathAddToStack(int i,int j,ElemType temp,ZJC_Stack &robot) //因为要修改值，所以取地址，开始没加取地址符号，栈顶元素一直是(1,1) 127 { 128 temp.x = i,temp.y = j; 129 Push(robot,temp); 130 MAP[i][j] = 2; //标记已经走过该格子了,当初想是否需要用其他标记，实际上不需要的，既然标记2，那么证明当然可以走过(不是墙)! 131 } 132 void MAZH_SOLVE(int endx,int endy) //解决迷宫问题函数,参数为终点的坐标 133 { 134 int i = 1,j = 1; //起点坐标 135 ZJC_Stack robot; //定义栈； 136 if(InitStack( robot ) ) //初始化栈 137 printf(" 栈的初始化完成.... "); 138 ElemType CurrentPos ; //当前位置 139 ElemType start; //初始位置的相关信息 140 ElemType temp; //暂时用的 141 start.x = i; 142 start.y = j; 143 temp = start; 144 //start.track = true; //Robot站在初始位置，初始位置已经走过 145 MAP[i][j] = 2; //走过的标记为2 146 Push(robot,start); //初始位置入栈 147 printf(" 开始寻路.... "); 148 do //主要寻路算法： 149 { 150 151 CurrentPos = GetTop(robot); 152 i = CurrentPos.x; 153 j = CurrentPos.y; 154 printf(" 寻路过程如下栈顶元素的 x = %d ,y = %d.... ",i,j); 155 if(MAP[i][j+1] == 1) //表明向下一格走得通 156 { 157 printf(" 向下能走动"); //向下前进一步，压栈，标记 158 j++; 159 PathAddToStack(i,j,temp,robot); 160 } 161 else if( MAP[i + 1][j] == 1) 162 { 163 printf(" 向右能走动"); 164 i++; 165 PathAddToStack(i,j,temp,robot); 166 } 167 else if(MAP[i - 1][j] == 1) 168 { 169 printf(" 向左能走动"); 170 i--; 171 PathAddToStack(i,j,temp,robot); 172 } 173 else if(MAP[i][j - 1] == 1) 174 { 175 printf(" 向上能走动"); 176 j--; 177 PathAddToStack(i,j,temp,robot); 178 } 179 else //都走不动 180 { 181 printf(" 都走不动，退栈"); 182 Pop(robot,temp); 183 } 184 185 }while( GetTop(robot).x != endx || GetTop(robot).y != endy); //只要栈顶元素的x,y不等于终点坐标的x,y,则一直循环找路径 186 printf(" 完成! "); 187 Print_Path(robot); //打印出坐标值 188 } 189 int _tmain(int argc, _TCHAR* argv[]) //入口函数 190 { 191 MAZH_SOLVE(7,7); 192 return 0; 193 }
其实在开始判断一下起点与终点的相对位置，选择不同的方案，这样可以减少后面的某些判断次数，提高效率。
比如我的这张地图中，就应该优先判断右下，因为终点在右下角。开始判断一下相对位置，后面修改下if条件句的顺序，就能提高效率了。
运行结果：
