基于栈的C 语言迷宫问题与实现 一． 问题描述 多年以来，迷宫问题一直是令人感兴趣的题目。实验心理学家训练老鼠在迷宫中寻找食物。许多神秘主义小说家也曾经把英国乡村花园迷宫作为谋杀现场。于是，老鼠过迷宫问题就此产生，这是一个很有趣的计算机问题，主要利用 “栈”是老鼠通过尝试的办法从入口穿过迷宫走到出口。 迷宫只有两个门，一个叫做入口，另一个叫做出口。把一只老鼠从一个无顶盖的大盒子的入口处赶进迷宫。迷宫中设置很多隔壁，对前进方向形成了多处障碍，在迷宫的唯一出口处放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口。求解迷宫问题，即找出从入口到出口的路径。 一个迷宫可用上图所示方阵[m,n]表示，0 表示能通过，1 表示不能通过。现假设耗子从左上角[1,1]进入迷宫，编写算法，寻求一条从右下角[m,n] 出去的路径。下图是一个迷宫的示意图： 迷宫示意图 二． 算法基本 思 想 迷宫问题是栈应 用的一个典 型 例 子。求解过程 可采 用回 溯 法。回 溯 法是一种 不断 试探 且及 时 纠 正 错 误 的搜 索 方法。从入口出发 ，按 某 一方向向前探 索 ，若 能走通（ 未 走过的），即某 处可以到达，则 到达新 点 ，否 则 试探 下一方向 ; 若 所有的方向均 没 有通路，则 沿 原 路返回 前一点 ，换 下一个方向再 继 续 试探 ，直到所有可能的通路都 探 索 到，或 找到一条通路，或无路可走又 返 回 到入口点 。 在求解过程 中，为了保 证 在到达某 一点 后 不能向前继 续 行 走（ 无路） 时 ，能正 确 返 回 前入口出口一点以便继续从下一个方向向前试探，则需要用一个栈保存所能够到达的每一点的下标及从该点前进的方向，栈中保存的就是一条迷宫的通路。 为了确保程序能够终止，调整时，必须保证曾被放弃过的填数序列不被再次试验，即要求按某种有序模型生成填数序列。给解的候选者设定一个被检验的顺序，按这个顺序逐一生成候选者并检验。 三． 主要数据结构 1.方阵栈： #define STACK_INI_SIZE 100 typedef struct { int *top; //指向栈的顶端域 int *base; //指向栈的低端域 int length; //栈的长度 int stacksize; //栈的最大长度 }sqstack; 2．产生迷宫的矩阵二维数组 为了使每一个迷宫存在迷宫的边界和两个端口：入口、出口，设置了一个二维数组，在迷宫的周边定义为1，使得迷宫存在边界，并在（1...
