迷宫算法

迷宫算法Struct position{ 迷宫算法算法思想:findpath首先创建一个足够大的堆栈，然后对偏移量数组进行初始化，并在迷宫周围增加一圈障碍物。在while循环中，从当前位置here出发，按下列次序来选择下一个移动位置：向右、向下、向左、向上。如果能够移动到下一个位置，则将当前位置放入堆栈path，并移动到下一个位置。如果找不到下一个可移动的位置，则退到前一个位置。如果无法回退一个位置（即堆栈为空），则表明不存在通往出口路径。当回退至堆栈的顶部位置（next）时，可以重新选择另一个可能的相邻位置，这可利用n...

Struct position{ 迷宫算法算法思想:findpath首先创建一个足够大的堆栈，然后对偏移量数组进行初始化，并在迷宫周围增加一圈障碍物。在while循环中，从当前位置here出发，按下列次序来选择下一个移动位置：向右、向下、向左、向上。如果能够移动到下一个位置，则将当前位置放入堆栈path，并移动到下一个位置。如果找不到下一个可移动的位置，则退到前一个位置。如果无法回退一个位置（即堆栈为空），则表明不存在通往出口路径。当回退至堆栈的顶部位置（next）时，可以重新选择另一个可能的相邻位置，这可利用next和here来推算。注意here是next的一个邻居。对下一个移动位置选择可用以下代码来实现： If(next.row==here.row)//推算next可移动位置的个数 Option=2+next.col-here.col; else option=3+next.row; Struct position{//位置 int row;//行 Int col;//列 }position; Status FindPath() {//寻找从位置（1，1）到出口（m,m）的路径 Position offset[4]； Offset[0].row=0;offset[0].col=1;//向右 Offset[1].row=1;offset[1].col=0;//向下 Offset[2].row=0;offset[2].col=-1;//向左 Offset[3].row=-1;offset[3].col=0;//向上 //在迷宫周围增加一圈障碍物 for(int i=0;i<=m+1;i++) { maze[0][i]=maze[m+1][i]=1;//底和顶 maze[i][0]=maze[i][m+1]=1;//左和右 } //优点：是程序不必处理边界条件，简化代码设计。 Path=new Stack(m*m-1); Position here; here.row=1; here.col=1; maze[1][1]=1;//阻止返回入口 int option=3; while(here.row!=m&&here.col!=m)//不是出口 {//寻找并移动到一个相邻位置 int r,c; while(option<=LastOption) { r=here.row+offset[option].row;//设置相邻格点 c=here.col+offset[option].col; if(maze[r][c]==0) break; option++; } //找到一个相邻位置了吗？ if(option<=LastOption) {//移动到maze[r][c] path->add(here); here.row=r; here.col=c; //设置障碍以阻止再次访问 maze[r][c]=1; option=0; } else{//没有可用的相邻位置，回溯（path->isEmpty()） return OK; Position next; Path->Delete(next);//退回至栈顶位置next If(next.row==here.row)//推算next可移动位置的个数 Option=2+next.col-here.col; else option=3+next.row; here=next; } return ERROR; } 最短路径算法算法思想：程序首先检查start 和finish是否相同，如果相同，则路径长度为0，程序终止。否则设置一堵由封锁位置构成的“围墙”，把网格包围起来。然后对offset数组进行初始化，并在起始位置上标记2。借助于队列Q并从位置start开始，直到移动到下start相距为1的网格位置，然后移动到start相距为2的网格位置，不断继续下去，直到到达位置finish或者无法继续移动到下一个新的、空白的位置。在后一种情况下，将不存在到达位置finish的路径，而在前一种情况下，位置finish将得到一个相应的编号。如果到达了finish，则可以利用网格上的标号来重构路径。路径上的位置（start除外）均被存储在数组path之中。 Status FindPath(Position start,Position finish,int &Pathlen,Position*path) {//寻找从start到finish的路径 if((start.row==finish.row)&&(start.col==finish.col)) { Pathlen=0; return OK; } Position offset[4]； Offset[0].row=0;offset[0].col=1;//向右 Offset[1].row=1;offset[1].col=0;//向下 Offset[2].row=0;offset[2].col=-1;//向左 Offset[3].row=-1;offset[3].col=0;//向上 //在迷宫周围增加一圈障碍物 for(int i=0;i<=m+1;i++) { maze[0][i]=maze[m+1][i]=1;//底和顶 maze[i][0]=maze[i][m+1]=1;//左和右 } int NumOfNbr=4;//一个网络个位置的相邻位置数 Position here,nbr; here.row=start.row; here.col=start.col; Maze[start.row] [start.col]=2;//封锁初始位置 LinkQueueQ; Do {//标记相邻位置 for(int i=0;i< NumOfNbr;i++) { nbr.row=here.row+offset[option].row; nbr.col=here.col+offset[option].col; //设置相邻格点 if(maze[nbr.row][ nbr.col]==0)//通路，且未被标记 { maze[nbr.row][ nbr.col]=maze[here.row][ here.col]+1; if((nbr.row==finish.row)&&( nbr.col==finish.col)) break;//找到宝藏完成标记 Q.add(nbr); }//if结束 }//for结束 //已到达finish吗？ if((nbr.row==finish.row)&&( nbr.col==finish.col)) break; //未到达finish,可移动到nbr吗？ If(Q.IsEmpty()) return ERROR; Q.delete(here); }while(OK) //构造路径 PathLen=maze[finish.row][ finish.col]-2; Path=new Position[Pathlen]; //回溯自finish here=finish; for(int j=pathLen-1;j>=0;j--) { path[j]=here; //寻找前一个位置 for(int i=0;i< NumOfNbr;i++) { nbr.row=here.row+offset[option].row; nbr.col=here.col+offset[option].col; if(maze[nbr.row][ nbr.col]==j+2) break; } here=nbr;//移动到前一位置 } return OK; }

                    本文档为【迷宫算法】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

迷宫算法

你可能还喜欢