主题:跪求,迷宫
1,问题描述
以一个m*n的长方阵表示迷宫,0和1分别表示迷宫中的通路和障碍。设计一个程序,对任意设定的迷宫,求出一条从入口到出口的通路,
或得出没有通路的结论。
2,基本要求
(1)实现一个以链表作存储结构的栈类型,然后编写一个求解迷宫的非递归程序。球的的通路以三元组(i,j,d)的形式输出,
其中:(i,j)指示迷宫中的一个坐标,d表示走到下一坐标的方向。
(2)编写递归形式的算法,求得迷宫中所有可能 的通路;
(3)以方阵形式输出迷宫及其通路。
3,测试数据
左上角(1,1)为入口,右下角(m,n)为出口。
4,实现提示
计算机解迷宫通常用的是“穷举求解”方法,即从入口出发,顺着某一个方向进行探索,若能走通,则继续往前进;
否则,沿原路退回,换一个方向继续探索,直至出口位置,求得一条通路。假如所有可能的通路都探索到而未能达到出口,
则所设定的迷宫没有通路。
可以二维数组存储迷宫数据,通常设定入口点的下标为(1,1),出口点的下标为(m,n).为处理方便起见,可在迷宫的四周加一圈障碍。
对于迷宫总任一位置,均可约定有东、南、西、北四个方向可通。
以一个m*n的长方阵表示迷宫,0和1分别表示迷宫中的通路和障碍。设计一个程序,对任意设定的迷宫,求出一条从入口到出口的通路,
或得出没有通路的结论。
2,基本要求
(1)实现一个以链表作存储结构的栈类型,然后编写一个求解迷宫的非递归程序。球的的通路以三元组(i,j,d)的形式输出,
其中:(i,j)指示迷宫中的一个坐标,d表示走到下一坐标的方向。
(2)编写递归形式的算法,求得迷宫中所有可能 的通路;
(3)以方阵形式输出迷宫及其通路。
3,测试数据
左上角(1,1)为入口,右下角(m,n)为出口。
4,实现提示
计算机解迷宫通常用的是“穷举求解”方法,即从入口出发,顺着某一个方向进行探索,若能走通,则继续往前进;
否则,沿原路退回,换一个方向继续探索,直至出口位置,求得一条通路。假如所有可能的通路都探索到而未能达到出口,
则所设定的迷宫没有通路。
可以二维数组存储迷宫数据,通常设定入口点的下标为(1,1),出口点的下标为(m,n).为处理方便起见,可在迷宫的四周加一圈障碍。
对于迷宫总任一位置,均可约定有东、南、西、北四个方向可通。