迷宫求解问题分析(C语言).ppt

《迷宫求解问题分析(C语言).ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第21章迷宫求解问题描述问题分析及实现开发过程常见问题及解决第21章迷宫求解问题描述问题分析及实现开发过程常见问题及解决第21章迷宫求解问题描述问题分析及实现开发过程常见问题及解决第21章迷宫求解问题描述问题分析及实现开发过程常见问题及解决迷宫求解C语言的功能是强大的，可以实现很多有意义的问题的求解。比如算法领域的经典问题——迷宫求解。在一个M×N的迷宫中，给定一个入口，一个出口，如何从入口走到出口？本章就实现了这一算法。21.1问题描述以一个m×n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。对任意设定的迷宫，求出一条从入口到出口的通路并输出所经过的坐标点，或得出没有通路的结论。

2、21.2问题分析及实现21.2.1问题分析21.2.2问题实现21.2.3程序运行21.2问题分析及实现由问题描述可知，我们要实现的是打印从坐标A，走到坐标B，要绕过路障走一条路径出来。简单举例：从左向右走动，中间有障碍物，此时，需要向上再向右，或向下再向右，只有绕过左与右之间的障碍物，才可以顺利从左走至右，以下将仔细地分析问题并实现算法。21.2.1问题分析我们的将要开发的程序，就是设置一个迷宫（m×n）,并设置入口点，出口点，从出口点走向入口点，将途经的坐标记录到“栈”底，在找到路径时，将弹出栈顶元素，此时，就是所有途经的坐标点。21.2.2问题实现本小节就来通过编程求解迷宫问题，实

3、现的代码如下。1.采用结构体保存过程数据通过定义两个结构体类型，分别记录栈中的走过的坐标及走过的方向，采用结构体实现栈的存储。那么，根据这个思路，代码如下（代码21-1.txt）。21.2.2问题实现2.输出结果将结果输出至屏幕，以循环打印的方式，调用标准输入输出函数printf,将结果回显。代码如下（代码21-2.txt）。21.2.2问题实现01/*输出路径*/02voidOutputPath(PSeqStackst)03{04DataTypeelement;05printf("出迷宫的路径是:");06while(!isEmptyStack_seq(st))07{08e

4、lement=Top_seq(st);09Pop_seq(st);10printf("路过的节点坐标是:第%d行第%d列",element.x,element.y);/*打印路径上的每一点*/11}12}21.2.2问题实现3.求解经过的坐标点及方向从入口点开始，依次试探四个方向，只要某个方向没有障碍，则继续这个方向，并将这个方向不是障碍物的点做为下一个当前点，循环直到到达入口点。代码如下（代码21-3.txt）21.2.3程序运行单击【调试】工具栏中的按钮，即可输出以下运行结果。21.3开发过程常见问题及解决开发过程常见问题及解决办法如下，仅供参考。⑴在程序中，如何表示一个坐标点呢

5、？方法很简单：只需要用一对变量即可保存。即：一个变量保存横坐标，另外一个变量保存纵坐标。⑵此程序的另一难点就是，方向如何表示？我们知道，水平方向有两个（左右），垂直方向也有两个（上下），所以方向就用8个变量可以表示出来。