1/*draw*/ /*寻找迷宫通路程序*/ i sqstktp *s int maze [M2][N2 struct moved move [8] Inmage(maze);/*初始化迷宫数组*/ s=(sqstktp )malloc(sizeof (sqstktp)): inistack(s);/*初始化栈*/ Ninove(move);/*初始化方向位移数组*/ path(maze,move,s);/*绘制作出通路标记的迷宫*/ 3、迷宫最短路径问题 [问题描述]在第2题给出的条件基础上,要求设计一个算法,寻找一条 从迷宫入口到出口的最短路径。输出信息的要求同第2题 [设计思想]一般走迷宫的方法是只要找出一条通路即可,至于这条通 路是怎样形成的,并没有关系。由于走迷宫的方法是采用试探法,因此第 步试探的方法非常重要,它决定了通路的可能走向。例如第一步向东走与向 东南走,最终形成的通路一般是不一样的。本题是在一般走迷宫的方法上 更进一步要求找出一条最短的路径,而不论起始试探的方位为何 算法的基本思想是:从迷宫的入口[1][1]出发,向四周搜索,记下所有 步能到达的坐标点p11,p12,……,plk1(0≤k1≤3);然后依次从 pl1l,…,plkl出发向四周搜索,几下所有从入口点出发,经过两部可以到 达的坐标点p21,……,p2k2(0≤K2≤5);依次进行下去,一直到达迷宫的出 口处[m][n]。然后从出口出演搜索路径回溯直至入口点,这样就找到了从入 口到出口的一条最短路径 在本算法中,搜索[i[j点周围8个方向的坐标点,以决定那些坐标点 是可以到达的,方法同上机实习题2。这里只是需要解决搜索路径的保存问 在搜索过程中必须记下每一个可到达的坐标点,以便从这些点出发继续 向四周搜索。由于先到达的点将作为新的起点先进新搜索,故须采用一个先 进先出的队列来保存已到达的坐标点。对于每一个记录下来的坐标点,还需 同时保存是从哪一个坐标点出发到达的(该坐标点肯定已在队列中了)。另 外搜索结束后,还需从出口向入口回溯,以寻找一条通路,因此尽管采用队 列形式,但每一个出发点并不真正离开队列(或者说并不真正从队列中将其 删除),只是取其值作为搜索的出发点。这样我们采用一个结构数组 queue[] 来做该队列的存储空间。因为迷宫中的每一个点至多被访问一次,因此printf(“\n”); } /*draw*/ /*寻找迷宫通路程序*/ void main( ) { sqstktp *s; int maze[M2][N2]; struct moved move[8]; inimaze(maze); /*初始化迷宫数组*/ s=(sqstktp )malloc(sizeof(sqstktp)); inistack(s); /*初始化栈*/ inimove(move); /*初始化方向位移数组*/ path(maze,move,s); /*绘制作出通路标记的迷宫*/ }/*main*/ 3、迷宫最短路径问题 [问题描述]在第 2 题给出的条件基础上，要求设计一个算法，寻找一条 从迷宫入口到出口的最短路径。输出信息的要求同第 2 题。 [设计思想] 一般走迷宫的方法是只要找出一条通路即可，至于这条通 路是怎样形成的，并没有关系。由于走迷宫的方法是采用试探法，因此第一 步试探的方法非常重要，它决定了通路的可能走向。例如第一步向东走与向 东南走，最终形成的通路一般是不一样的。本题是在一般走迷宫的方法上， 更进一步要求找出一条最短的路径，而不论起始试探的方位为何。 算法的基本思想是：从迷宫的入口[1][1]出发，向四周搜索，记下所有 一步能到达 的坐标 点 p11,p12,…… ，p1k1(0≤k1 ≤3);然 后依次从 p11,……,p1k1 出发向四周搜索，几下所有从入口点出发，经过两部可以到 达的坐标点 p21,……，p2k2(0≤K2≤5);依次进行下去，一直到达迷宫的出 口处[m][n]。然后从出口出演搜索路径回溯直至入口点，这样就找到了从入 口到出口的一条最短路径。 在本算法中，搜索[i][j]点周围 8 个方向的坐标点，以决定那些坐标点 是可以到达的，方法同上机实习题 2。这里只是需要解决搜索路径的保存问 题。 在搜索过程中必须记下每一个可到达的坐标点，以便从这些点出发继续 向四周搜索。由于先到达的点将作为新的起点先进新搜索，故须采用一个先 进先出的队列来保存已到达的坐标点。对于每一个记录下来的坐标点，还需 同时保存是从哪一个坐标点出发到达的（该坐标点肯定已在队列中了）。另 外搜索结束后，还需从出口向入口回溯，以寻找一条通路，因此尽管采用队 列形式，但每一个出发点并不真正离开队列（或者说并不真正从队列中将其 删除），只是取其值作为搜索的出发点。这样我们采用一个结构数组 queue[] 来做该队列的存储空间。因为迷宫中的每一个点至多被访问一次，因此