C语言课件 第21 22章.ppt

第21章 迷宫求解,问题描述 问题分析及实现 开发过程常见问题及解决,第21章 迷宫求解,问题描述 问题分析及实现 开发过程常见问题及解决,第21章 迷宫求解,问题描述 问题分析及实现 开发过程常见问题及解决,第21章 迷宫求解,问题描述 问题分析及实现 开发过程常见问题及解决,迷宫求解,c语言的功能是强大的，可以实现很多有意义的问题的求解。比如算法领域的经典问题迷宫求解。在一个mn的迷宫中，给定一个入口，一个出口，如何从入口走到出口？本章就实现了这一算法。,21.1 问题描述,以一个mn的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。对任意设定的迷宫，求出一条从入口到出口的通路并输出所经过的坐标点，或得出没有通路的结论。,21.2.1 问题分析 21.2.2 问题实现 21.2.3 程序运行,21.2 问题分析及实现,由问题描述可知，我们要实现的是打印从坐标a，走到坐标b，要绕过路障走一条路径出来。简单举例：从左向右走动，中间有障碍物，此时，需要向上再向右，或向下再向右，只有绕过左与右之间的障碍物，才可以顺利从左走至右，以下将仔细地分析问题并实现算法。,21.2.1 问题分析,我们的将要开发的程序，就是设置一个迷宫（mn）,并设置入口点，出口点，从出口点走向入口点，将途经的坐标记录到“栈”底，在找到路径时，将弹出栈顶元素，此时，就是所有途经的坐标点。,21.2.2 问题实现,本小节就来通过编程求解迷宫问题，实现的代码如下。 1. 采用结构体保存过程数据 通过定义两个结构体类型，分别记录栈中的走过的坐标及走过的方向，采用结构体实现栈的存储。那么，根据这个思路，代码如下（代码21-1.txt）。,21.2.2 问题实现,2. 输出结果 将结果输出至屏幕，以循环打印的方式，调用标准输入输出函数printf,将结果回显。代码如下（代码21-2.txt）。,21.2.2 问题实现,01 /*输出路径*/ 02 void outputpath(pseqstack st) 03 04 datatype element; 05 printf(“nn出迷宫的路径是:n“); 06 while(!isemptystack_seq(st) 07 08 element = top_seq(st); 09 pop_seq(st); 10 printf(“n路过的节点坐标是: 第%d行 第%d列“, element.x, element.y); /* 打印路径上的每一点*/ 11 12 ,21.2.2 问题实现,3. 求解经过的坐标点及方向 从入口点开始，依次试探四个方向，只要某个方向没有障碍，则继续这个方向，并将这个方向不是障碍物的点做为下一个当前点，循环直到到达入口点。代码如下（代码21-3.txt）,21.2.3 程序运行,单击【调试】工具栏中的按钮，即可输出以下运行结果。,21.3 开发过程常见问题及解决,开发过程常见问题及解决办法如下，仅供参考。 在程序中，如何表示一个坐标点呢？方法很简单：只需要用一对变量即可保存。即：一个变量保存横坐标，另外一个变量保存纵坐标