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

北京邮电大学电信工程学院计算机技术中心北京邮电大学电信工程学院计算机技术中心北京邮电大学电信工程学院计算机技术中心北京邮电大学电信工程学院计算机技术中心北京邮电大学电信工程学院计算机技术中心北京邮电大学电信工程学院计算机技术中心北京邮电大学电信工程学院计算机技术中心北京邮电大学电信工程学院计算机技术中心北京邮电大学电信工程学院计算机技术中心北京邮电大学电信工程学院计算机技术中心北京邮电大学电信工程学院计算机技术中心北京邮电大学电信工程学院计算机技术中心北京邮电大学电信工程学院计算机技术中心北京邮电大学电信工程学院计算机技术中心迷宫问题迷宫问题主要内容1．问题分析2．递归算法3．非递归算法1．问题分析o迷宫求解这是一个找出口的问题。自相似性表现在什么地方？每走一步的探测方式。由于计算机很傻，只能通过穷举方式找出口，怎么找法？沿着一个方向走下去，如果走不通，则换个方向走；四个方向都走不通，则回到上一步的地方，换个方向走；依次走下去，直到走到出口。1．问题分析设置迷宫为二维数组，数组的值是描述迷宫：代表未走过的路径代表走不通的路径代表路径1：代表墙1．问题分析1．问题分析-1-1-1-1-1-1-1-1-1-1-100-1000-10-1-100-1000-10-1-10000-1-100-1-10-1-1-10000-1-1000-10000-1-10-1000-100-1-10-1-1-10-1-10-1-1-10000000-1-1-1-1-1-1-1-1-1-1-1设置搜索方向顺序是东、南、西、北01(x,y)02(x-1,y)03(x,y-1)04(x,y+1)05(x+1,y)06东07北081．问题分析明确递归函数的意义1每一步的走法2intnext(intarr[][10],Pointcur,Pointend)；32．递归算法迷宫求解每走一步：如果当前位置=出口，结束否则：假设当前位置为路径；如果东面未走过：向东走一步如果南面未走过：向南走一步如果西面未走过：向西走一步如果北面未走过：向北走一步设置当前位置走不通，回溯intnext(intarr[][10],Pointcur,Pointend){ if((cur.x==end.x)(cur.y==end.y)) return1; else{ arr[cur.x][cur.y]=2; if(arr[cur.x+1][cur.y]==0)//东{ Pointt;t.x=cur.x+1;t.y=cur.y;if(next(arr,t,end)) return1; } if(arr[cur.x][cur.y+1]==0)//南{ Pointt;t.x=cur.x;t.y=cur.y+1; if(next(arr,t,end))return1; } …//西…//北arr[cur.x][cur.y]=1; return0; }北京邮电大学电信工程学院计算机技术中心北京邮电大学电信工程学院计算机技术中心北京邮电大学电信工程学院计算机技术中心北京邮电大学电信工程学院计算机技术中心北京邮电大学电信工程学院计算机技术中心北京邮电大学电信工程学院计算机技术中心北京邮电大学电信工程学院计算机技术中心北京邮电大学电信工程学院计算机技术中心北京邮电大学电信工程学院计算机技术中心北京邮电大学电信工程学院计算机技术中心北京邮电大学电信工程学院计算机技术中心北京邮电大学电信工程学院计算机技术中心北京邮电大学电信工程学院计算机技术中心北京邮电大学电信工程学院计算机技术中心