【数据结构】c语言基于堆栈实现回溯法自动走迷宫

迷宫的坐标用二维数组表示，此外还需要一个当前坐标缓冲区，表示当前位置，我使用的是b[3]数组，第三个空间用来表示这个格子被走了几次

#include "stdafx.h"
#include
#include
using namespace std;#define MAXSIZE 100
#define ERROR 0
#define OK 1typedef char Elemtype;//这里修改数组的数据类型
typedef int Status;/*算法描述：1.每个格子都按照右上左右的顺序检查下一步要走的格子2.b数组存放当前信息，0表示x坐标1表示y坐标，2表示走过该格子的次数3.若检测到该格子可以走并且没走过则入栈并且走上这个格子4.假如遇到了思路不能走了就退栈返回原来的道路重新寻找新的道路5.一开始就设定一个胜利坐标，假如走到了这个胜利坐标就算胜利
*//*堆栈测试成功*/
//栈数据结构
//我们规定top指向栈顶元素，bottom为空，当top==bottom的时候栈空
typedef struct Stack {int coord[MAXSIZE][3];  //0表示x坐标，1表示y坐标，2表示走过这个格子的次数int top, bottom;        //这里bottom和top赋初值为-1，这样就可以从0开始填入数据
}*st;//初始化堆栈并且把数组元素都变为0,top和bottom赋初值为-1
Status init_s(st s) {for (int i = 0; i < MAXSIZE; i++) {for (int j = 0; j < 3; j++) {s->coord[i][j] = 0;}}s->top = s->bottom = -1;return OK;
}//判断栈是不是为空栈，如果是空栈返回0，否则返回1
Status empty(st s) {if (s->top == s->bottom) {return ERROR;//栈空}else {return OK;}
}//入栈操作
//先top++然后写入数据
//c数组用来存储当前可以写入的坐标
Status push(st s, int c[3]) {s->top++;if (s->top >= MAXSIZE) {cout << "栈满，已经不可以继续让里面添加元素了" << endl;s->top--;return ERROR;}cout << "三个值分别是：";for (int i = 0; i < 3; i++) {s->coord[s->top][i] = c[i];cout << c[i];}return OK;
}//出栈操作
//先弹出top指向的元素，然后top--
//b数组用来存储当前位置的xy和行走次数
Status pop(st s,int b[3]) {if (empty(s) == 0) {//如果栈空的话就不能弹栈cout << "栈空，无法弹出" << endl;return ERROR;}else {//出栈操作，把退出的坐标赋值给当前坐标数组for (int i = 0; i < 3; i++) {b[i] = s->coord[s->top][i];}s->top--;return OK;}
}
//显示堆栈所有内容
void test(st s) {int t = s->top;cout << "堆栈里面的内容如下：" << endl;cout << "x,y" << endl;while (t != -1) {cout << s->coord[t][0] << "," << s->coord[t][1]<走出了迷宫！！" << endl;return 0;
}

基本思路就是以一定的顺序检查上下左右格子是否可以走，如果可以走的话，就把之前的一步压入堆栈中，当遇到无路可走的情况的时候，就退栈然后继续检查有没有可以走的路，知道走出迷宫为止，如果没有可以走出迷宫的路的话，栈会被弹空然后没有可以走的路了。最后调试的结果如下：