求解迷宫问题-(c语言-很详细哦).doc

上传人:豆**** 文档编号:28490709 上传时间:2022-07-28 格式:DOC 页数:5 大小:14.50KB
返回 下载 相关 举报
求解迷宫问题-(c语言-很详细哦).doc_第1页
第1页 / 共5页
求解迷宫问题-(c语言-很详细哦).doc_第2页
第2页 / 共5页
点击查看更多>>
资源描述

《求解迷宫问题-(c语言-很详细哦).doc》由会员分享,可在线阅读,更多相关《求解迷宫问题-(c语言-很详细哦).doc(5页珍藏版)》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、精品文档,仅供学习与交流,如有侵权请联系网站删除 求迷宫问题就是求出从入口到出口的路径。在求解时,通常用的是“穷举求解”的方法,即从入口出发,顺某一方向向前试探,若能走通,则继续往前走;否则沿原路退回,换一个方向再继续试探,直至所有可能的通路都试探完为止。为了保证在任何位置上都能沿原路退回(称为回溯),需要用一个后进先出的栈来保存从入口到当前位置的路径。 首先用如图3.3所示的方块图表示迷宫。对于图中的每个方块,用空白表示通道,用阴影表示墙。所求路径必须是简单路径,即在求得的路径上不能重复出现同一通道块。为了表示迷宫,设置一个数组mg,其中每个元素表示一个方块的状态,为0时表示对应方块是通道,

2、为1时表示对应方块为墙,如图3.3所示的迷宫,对应的迷宫数组mg如下: int mgM+1N+1= /*M=10,N=10*/1,1,1,1,1,1,1,1,1,1,1,0,0,1,0,0,0,1,0,1,1,0,0,1,0,0,0,1,0,1,1,0,0,0,0,1,1,0,0,1,1,0,1,1,1,0,0,0,0,1,1,0,0,0,1,0,0,0,0,1,1,0,1,0,0,0,1,0,0,1,1,0,1,1,1,0,1,1,0,1,1,1,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1 ; 伪代码:c语言描述如下:void mgpath() /*路径为:(1,

3、1)-(M-2,N-2)*/ int i,j,di,find,k; top+; /*初始方块进栈*/ Stacktop.i=1; Stacktop.j=1; Stacktop.di=-1; mg11=-1; while (top-1) /*栈不空时循环*/ i=Stacktop.i; j=Stacktop.j; di=Stacktop.di; if (i=M-2 & j=N-2) /*找到了出口,输出路径*/ printf(迷宫路径如下:n); for (k=0;k=top;k+) printf(t(%d,%d),Stackk.i,Stackk.j); if (k+1)%5=0) printf

4、(n); printf(n); return; find=0; while (di4 & find=0) /*找下一个可走方块*/ di+; switch(di) case 0:i=Stacktop.i-1; j=Stacktop.j; break; case 1:i=Stacktop.i; j=Stacktop.j+1; break; case 2:i=Stacktop.i+1; j=Stacktop.j; break; case 3:i=Stacktop.i; j=Stacktop.j-1; break; if (mgij=0) find=1; if (find=1) /*找到了下一个可走方块*/ Stacktop.di=di; /*修改原栈顶元素的di值*/ top+; /*下一个可走方块进栈*/ Stacktop.i=i; Stacktop.j=j; Stacktop.di=-1; mgij=-1; /*避免重复走到该方块*/ else /*没有路径可走,则退栈*/ mgStacktop.iStacktop.j=0; /*让该位置变为其他路径可走方块*/ top-; printf(没有可走路径!n); 【精品文档】第 5 页

展开阅读全文
相关资源
相关搜索

当前位置:首页 > 教育专区 > 小学资料

本站为文档C TO C交易模式,本站只提供存储空间、用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。本站仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知淘文阁网,我们立即给予删除!客服QQ:136780468 微信:18945177775 电话:18904686070

工信部备案号:黑ICP备15003705号© 2020-2023 www.taowenge.com 淘文阁