2025年整理c语言实现--迷宫问题

c 语言实现迷宫问题数据结构试验——迷宫问题（一）基本问题这是心理学中的一个经典问题。心理学家把一只老鼠从一个无顶盖的大盒子的入口处放入，让老鼠自行找到出口出来。迷宫中设置很多障碍阻止老鼠前行，迷宫唯一的出口处放有一块奶酪，吸引老鼠找到出口。简而言之，迷宫问题是解决从布置了许多障碍的通道中寻找出路的问题。本题设置的迷宫如图 1 所示。图 1 迷宫示意图迷宫四周设为墙；无填充处，为可通处。设每个点有四个可通方向，分别为东、南、西、北(为了清楚，以下称“上下左右”)。左上角为入口。右下角为出口。迷宫有一个入口，一个出口。设计程序求解迷宫的一条通路。以一个 m×n 的数组 mg 表示迷宫，每个元素表示一个方块状态，数组元素 0 和 1 分别表示迷宫中的通路和障碍。迷宫四周为墙，对应的迷宫数组的边界元素均为 1。根据题目中的数据，设置一个数组 mg如下intmg[M+2][N+2]={1,1,1,1,1,1,1,1},{1,0,0,1,0,0,0,1},{1,1,0,0,0,1,1,1},{1,0,0,1,0,0,0,1},{1,0,0,0,0,0,0,1},{1,1,1,1,1,1,1,1}};在算法中用到的栈采纳顺序存储结构，将栈定义为Struct{inti;//当前方块的行号intj;//当前方块的列号intdi;//di 是下一个相邻的可走的方位号}st[MaxSize];//定义栈inttop=-1//初始化栈3 设计运算算法要寻找一条通过迷宫的路径，就必须进行试探性搜索，只要有路可走就前进一步，无路可进，换一个方向进行尝试；当所有方向均不可走时，则沿原路退回一步（称为回溯），重新选择未走过可走的路，如此继续，直至到达出口或返回入口（没有通路）。在探究前进路径时，需要将搜索的踪迹记录下来，以便走不通时，可沿原路返回到前一个点换一个方向再进行新的探究。后退的尝试路径与前进路径正好相反，因此可以借用一个栈来记录前进路径。方向：每一个可通点有 4 个可尝试的方向，向不同的方向前进时，目的地的坐标不同。预先把 4 个方向上的位移存在一个数组中。如把上、右、下、左（即顺时针方向）依次编号为 0、1、2、3.其增量数组 move[4]如图 3 所示。move[4]x y0 -101 0 12 1 03 0 -1图 2 数组 move[4]方位示意图如下：通路：通路上的每一个点有 3 个属性：一个横坐标属性 i、一个列坐标属性 j 和一个方向属性 di，表示其下一点的位置。假如约定尝试的顺序为上、右、下、左（即顺时针方向），则每尝试一个方向不通时，di 值增 1，当 d 增至 4 时，表示此位置一定不是通路上的点，从栈中去...