迷宫旅行游戏复习课程.doc

《迷宫旅行游戏复习课程.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、精品好文档，推荐学习交流迷宫旅行游戏1项目简介迷宫只有两个门，一个门叫入口，另一个门叫出口。一个骑士骑马从入口走进迷宫，迷宫中设置很多墙壁，对前进方向形成了多处障碍。骑士需要在迷宫中寻找通路以到达出口。2设计思路迷宫问题的求解过程可以采用回溯法即在一定的约束条件下试探地搜索前进，若前进中受阻，则及时回头纠正错误另择通路继续搜索的方法。从入口出发，按某一方向向前探索，若能走通（未走过的），即某处可达，则到达新点，否则试探下一方向；若所有的方向均没有通路，则沿原路返回前一点，换下一个方向再继续试探，直到所有可能

2、的通路都探索到，或找到一条通路，或无路可走又返回到入口点。在求解过程中，为了保证在到达某一点后不能向前继续行走（无路）时，能正确返回前一点以便继续从下一个方向向前试探，则需要在试探过程中保存所能够到达的每一点的下标及从该点前进的方向，当找到出口时试探过程就结束了。为了确保程序能够终止，调整时，必须保证曾被放弃过的填数序列不被再次试验，即要求按某种有序模型生成填数序列。给解的候选者设定一个被检验的顺序，按这个顺序逐一生成候选者并检验。3数据结构迷宫问题是栈应用的一个典型例子。通过前面分析，我们知道在试探过程中

3、为了能够沿着原路逆序回退，就需要一种数据结构来保存试探过程中曾走过的点的下标及从该点前进的方向，在不能继续走下去时就要退回前一点继续试探下一个方向，栈底元素是入口，栈顶元素是回退的第一站，也即后走过的点先退回，先走过的点后退回，与栈的“后进选出，先进后出”仅供学习与交流，如有侵权请联系网站删除谢谢2精品好文档，推荐学习交流特点一致，故在该问题求解的程序中可以采用栈这种数据结构。在迷宫有通路时，栈中保存的点逆序连起来就是一条迷宫的通路，否则栈中没有通路。4程序清单程序提示：用二维数组表示二维迷宫中各个点是否有

4、通路，在二维迷宫里面，从出发点开始，每个点按四邻域计算，按照右、上、左、下的顺序搜索一下落脚点，有路则走，无路即退回前点再从下一个方向搜索，即可构成一有序模型。栈用顺序结构实现。可点击“编辑”-“显示比例”进行放大查看东汉-全图东汉-并州仅供学习与交流，如有侵权请联系网站删除谢谢2