迷宫求解(云南大学)
第1关:迷宫求解(栈)
任务描述
本关任务:编写一个能自动走出迷宫的程序。
相关知识
为了完成本关任务,你需要掌握:1.栈操作,2.迷宫求解。
迷宫
我们小时候都玩过迷宫,走迷宫可以说是非常有意思了。而在我们大脑里是如何对这个游戏进行思考的呢?其实我们在玩这个游戏的是,大多是一条路走到黑,如果到达出口那么就走出来了,如果是死胡同,那么回到刚才的分叉口,再找一条路再一条路走到黑,以此类推。而我们在实现迷宫求解的时候也是利用这种方法,这种方法又称作回溯法。
怎么实现
关于迷宫怎么回溯,这就要用到栈的特性.
,
例如在这个迷宫中0表示墙,1表示通道,起点是二维数组得[0,1],终点是[3,5]。在走迷宫过程中,当走到[3,1]位置时,发现前面已经无路可走,这时候就要回退一步,回退到哪呢?显然是[2,1],按照这种方法遍历在最坏的情况下遍历所有通路自然是可以走出迷宫的.
到这里不难想到,迷宫中前进一步就相当于一次入栈,回退一步就相当于一次出栈.
编程要求
本题中,会给出顺序栈
struct SeqStack{
T* row; // 行
T* col; //列
int top; // 栈顶元素编号
int max; // 最大节点数
};
和
SeqStack* SS_Create(int maxlen); //创建空栈
void SS_Free(SeqStack* ss); //释放栈
void SS_MakeEmpty(SeqStack* ss);//栈空
bool SS_IsFull(SeqStack* ss);//判断栈满
bool SS_IsEmpty(SeqStack* ss);//判