迷宫算法.doc

文档介绍：本人精心整理的文档,文档来自网络本人仅收藏整理如有错误还请自己查证!++:classBlock{public: intx; inty; //对应G矩阵中坐标 y行 x列 inti; intj; //对应B矩阵中坐标 i行j列 boolup; booldown; boolleft; boolright; //表示上下左右是否有墙0=有 intmark; //用于迷宫算法中的标识对于一个block每有一个方向为墙则mark+1 Block(); voidSet_ij(int,int); //设置对应B矩阵中坐标 voidSet_xy(int,int,int,int,int,int); //设置对应G矩阵中坐标 voidSet_udlr(Block[nn][nn],unsignedshort[Gr][Gc]); //设置updownleftright};//GrGc为像素矩阵的大小main函数会接受图像像素矩阵G[Gr][Gc]定标位置x1、y1、x2、y3入口坐标si、sj出口坐标ei、ej我们首先声明一个Block的矩阵B[nn][nn]其中nn为可设置常量表示矩阵大小每个矩阵单元对应着迷宫中的一个格子(迷宫可以看作nn*nn个格子组成的)然后调用Set_ij()函数为每一个矩阵单元添加其在B中的行列位置信息再调用Set_xy()函数设置每个矩阵单元对应图像中像素位置也就是对应迷宫的哪个格子比如说B[0][0]对应G[50][70]、B[0][1]对应G[50][120]现在我们调用Set_udlr()函数来计算每个矩阵单元对应的格子的上下左右是否有墙壁方法是这样的(以确定上方有没有墙为例其他方向类似):voidBlock::Set_udlr(BlockB[nn][nn],unsignedshortG[Gr][Gc]) { //G矩阵中表示黑色部分即墙壁 intt,xx1,xx2,yy1,yy2; //扫描参数 intisWall=0; //0代表不是墙当isWall大于可调常量ww时即认为有墙 //up if(i==0) //如果是第一行 { up=0; //设置上方是墙++mark;//该格子不能走的方向+1 } else //如果不是第一行 { //纵向扫描如图所示 yy1=y-(y-B[i-1][j].y)/6*5; yy2=y-(y-B[i-1][j].y)/6; for(t=yy1;t<yy2;++t) { if(G[t][x]==0) //如果该像素点为++isWall; //则isWall+1 } if(isWall>=ww)//如果扫描范围内有超过ww个为的像素点{ up=0; ++mark; } }..........}(DFS):template<classElemType>classStack{private: ElemType*storage; inttop; intmaxSize; voidDouble();public: Stack(intsize); ~Stack(); voidClear(); boolIsEmpty(); //判空 ElemTypeGetTop(); //取栈顶 voidPush(ElemType);//进栈 ElemTypePop(); //出栈}; 下面我们先将起点进栈然后按照上->下->左->右的优先顺序向可以走(即没有墙)的方向前进如果走向一个方向则将这个方向设为不能走同时将该方向走到的格子进栈并且将走到的格子回到上一格子的方向设为不能走这是为了不走回头路以及走不通后退时选择其他未走方向如果遇到上下左右都不能走的情况则退栈考虑上一步的其他方向如果走到了终点则结束如果无路可走且没到终点则退出如此就可以得到从入口到出口的一条路径最后我们将得到的路径存入M矩阵并用降序的数字序列表示具体代码如下://计算路径 intp,q; Stack<Block>s(100); Blockb; //起点为sisj终点为eiej (B[si][sj]); b=(