




全文预览已结束
下载本文档
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
迷宫问题王欣歆20080564一需求设计:以一个m*m 的方阵表示迷宫,0和1分别表示迷宫中的通路和障碍。设计一个程序,对任意设定的迷宫,求出一条从入口的通道,或得出没有通路的结论。二概要设计:存储结构:采用了数组以及结构体来存储数据,在探索迷宫的过程中用到的栈,属于顺序存储结构。/*八个方向的数组表示形式*/int move82=0,1,1,1,1,0,1,-1,0,-1,-1,-1,-1, 0,-1, 1;/*用结构体表示位置*/struct positionint x,y;position stackm*m+1;基本算法:走迷宫的过程可以模拟为一个搜索的过程:每到一处,总让它按东、东南、南、西南、西、西北、北、东北8个方向顺序试探下一个位置;如果某方向可以通过,并且不曾到达,则前进一步,在新位置上继续进行搜索;如果8个方向都走不通或曾经到达过,则退回一步,在原来的位置上继续试探下一位置。每前进或后退一步,都要进行判断:若前进到了出口处,则说明找到了一条通路;若退回到了入口处,则说明不存在通路。用一个字符类型的二维数组表示迷宫,数组中每个元素取值“0”(表示通路)或“1”(表示墙壁)。迷宫的入口点在位置(1,1)处,出口点在位置(m,m)处。设计一个模拟走迷宫的算法,为其寻找一条从入口点到出口点的通路。二维数组的第0行、第m+1行、第0列、第m+1列元素全置成“1”, 表示迷宫的边界;第1行第1列元素和第m行第m列元素置成“0”, 表示迷宫的入口和出口;其余元素值用随机函数产生。假设当前所在位置是(x,y)。沿某个方向前进一步,它可能到达的位置最多有8个。如果用二维数组move记录8个方向上行下标增量和列下标增量,则沿第i个方向前进一步,可能到达的新位置坐标可利用move数组确定: x=x+movei0 y=y+movei1从迷宫的入口位置开始,沿图示方向顺序依次进行搜索。在搜索过程中,每前进一步,在所到位置处做标记“h”(表示这个位置在通路上),并将该位置的坐标压入栈中。每次后退的时候,先将当前所在位置处的通路标记“h”改成死路标记“”(表示这个位置曾到达过但走不通,以后不要重复进入),然后将该位置的坐标从栈顶弹出。搜索到出口位置时,数组中那些值为“h”的元素形成一条通路。三详细设计:源程序:/*迷宫问题走迷宫的过程可以模拟为一个搜索的过程:每到一处,总让它按东、东南、南、西南、西、西北、北、东北个方向顺序试探下一个位置;如果某方向可以通过,并且不曾到达,则前进一步,在新位置上继续进行搜索;如果个方向都走不通或曾经到达过,则退回一步,在原来的位置上继续试探下一位置。 每前进或后退一步,都要进行判断:若前进到了出口处,则说明找到了一条通路;若退回到了入口处,则说明不存在通路。 用一个字符类型的二维数组表示迷宫,数组中每个元素取值“0”(表示通路)或“1”(表示墙壁)。迷宫的入口点在位置(1,1)处,出口点在位置(m,m)处。这个算法,为其寻找一条从入口点到出口点的通路。*/#include#include#include#includeint main()int m=1;while (m!=0)printf(输入m,使得为m*m的方阵迷宫(m0 输入0 时退出:)n);scanf (%d,&m);/*设定n*n的方阵迷宫*/*数组的形式表示八个方向*/int move82=0,1,1,1,1,0,1,-1,0,-1,-1,-1,-1, 0,-1, 1;/*用结构体表示位置*/struct positionint x,y;/*用于记录和输出迷宫探路中相关符号,包括1 .*/char mazem+2m+2;/*用栈来存储探路过程中的数据*/position stackm*m+1;int top;/*栈顶*/int i,x,y,ok;position p;/*二维数组的第0行、第m+1行、第0列、第m+1列元素全置成1,表示迷宫的边界;第1行第1列元素和第m行第m列元素置成0,表示迷宫的入口和出口;其余元素值用随机函数产生。*/srand(time(0);for(x=1;x=m;x+)for(y=1;y=m;y+)mazexy=48+rand()%2;maze11=0;mazemm=0;for(x=0;x=m+1;x+)mazex0=1;mazexm+1=1;for(y=0;y=m+1;y+)maze0y=1;mazem+1y=1;p.x=1;p.y=1;top=1;stacktop=p;maze11=.;/*开始探路 走迷宫的过程可以模拟为一个搜索的过程:每到一处,总让它按东、东南、南、西南、西、西北、北、东北个方向顺序试探下一个位置;如果某方向可以通过,并且不曾到达,则前进一步,在新位置上继续进行搜索;如果个方向都走不通或曾经到达过,则退回一步,在原来的位置上继续试探下一位置。 每前进或后退一步,都要进行判断:若前进到了出口处,则说明找到了一条通路;若退回到了入口处,则说明不存在通路。*/dop=stacktop;ok=0;i=0;while(ok=0)&(i0)&(p.x!=m)|(p.y!=m);/*输出探路结果*/if(top=0) printf(没有路径n);else printf(有路径n);/*输出探路迷宫留下的踪迹*/for(x=1;x=m;x+)printf(n);for(y=1;y=m;y+) printf(%c ,mazexy);printf(n); system(pause); 四调试分析:测试数据和结果
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2026年高考英语复习新题速递之应用文阅读理解(2025年7月)
- 知识题库-化工仪表知识考试题目及答案
- 技术大潮下的研发面试挑战:面试题库
- 细胞营销计划执行方案
- 胃癌术后病人护理查房
- 2019届高三人教版语文一轮复习课件:第三专题三第二节准确理解情境正确书写关键字
- 神经外科进修三个月汇报
- 系统解剖学消化系统详解
- 现代医院管理的创新思维
- 团建活动照片策划与呈现
- 跨界融合与个性化护肤
- 中医艾灸养生护理
- 2025届湖南省长沙市一中物理高一上期中达标检测模拟试题含解析
- 工程施工重点、难点分析及保证措施
- 2024城市电缆线路岩土工程勘察规范
- 变电站巡检维护服务方案
- 华为质量回溯(根因分析与纠正预防措施)模板
- 2023版评审准则和CNAS对照表
- CATIA CAA 二次开发详细教程(11) 程序的发布
- 分布式光伏发电项目可行性分析报告(方案)讲解演示模板ppt课件-图文
- 高空作业安全刷漆施工方案
评论
0/150
提交评论