数据结构编程《迷宫问题》.ppt

迷宫问题 迷宫问题 主要内容1 问题分析2 递归算法3 非递归算法 1 问题分析 1 问题分析 迷宫求解这是一个找出口的问题 自相似性表现在什么地方 每走一步的探测方式 由于计算机很傻 只能通过穷举方式找出口 怎么找法 沿着一个方向走下去 如果走不通 则换个方向走 四个方向都走不通 则回到上一步的地方 换个方向走 依次走下去 直到走到出口 1 问题分析 描述迷宫 1 设置迷宫为二维数组 数组的值是 1 代表墙0 代表未走过的路径1 代表走不通的路径2 代表路径 1 问题分析 1 问题分析 2 设置搜索方向顺序是东 南 西 北 x y x 1 y x y 1 x y 1 x 1 y 东 北 2 递归算法 明确递归函数的意义每一步的走法intnext intarr 10 Pointcur Pointend 迷宫求解 每走一步 1 如果当前位置 出口 结束2 否则 假设当前位置为路径 如果东面未走过 向东走一步如果南面未走过 向南走一步如果西面未走过 向西走一步如果北面未走过 向北走一步设置当前位置走不通 回溯 intnext intarr 10 Pointcur Pointend if cur x end x 3 非递归算法 程序步骤 1 当前位置入栈2 判断下一步是否可通 可通 则返回步骤1 不可通 换方向继续探索 3 若四周 均无通路 则当前位置出栈 从前一位置换方向搜索 voidMasePath intarr 10 Pointstart Pointend StackPointStack PointP start arr P x P y 2 do PointStack Push P if arr P x P y 1 0 arr P x P y 2 elseif arr P x 1 P y 0 arr P x P y 2 elseif arr P x P y 1 0 arr P x P y 2 elseif arr P x 1 P y 0 arr P x P y 2 else P PointStack Pop arr P x P y 1 P PointStack Pop while P x end x P y end y 辅助函数 打印迷宫voidPrintPath intarr 10 for inti 0 i 10 i for intj 0 j 10 j if arr i j 1 cout elseif arr i j 2 cout elsecout cout endl cout endl