迷宫算法(DFS) |
您所在的位置:网站首页 › 生成迷宫的算法有哪些 › 迷宫算法(DFS) |
1.如果采用堆栈进行迷宫探测,则称之为深度优先搜索(DFS),它和递归的探测思路是基本一致的,可以看成是递归方式的非递归版本; 2.采用队列进行迷宫探测,则是广度优先搜索(BFS),广度优先搜索法利用队列的特点,一层层向外扩展查找可走的方块,直到找到出口为止,最先找到的这个答案就必然是最短的。 如果打比喻来说,DFS更适合模拟机器人走迷宫的方式,看到一个方向是通的,就一直走下去,遇到死胡同就退回;BFS则好比一个人站在迷宫入口处,拿出一堆小探测器,每个小探测器帮他搜索一个可能的路径去寻找,第一个找到出口的探测器发出了反馈,那么这个人就按照这个小探测器找到的路径走迷宫就行了。 迷宫问题![]() ![]() 注意:这里走迷宫遵循右下左上的原则 ![]() ![]() Box结构体中的di的取值在1到3之间,表示的是dircet结构体数组的第几个元素,而direct结构体数组里面每个元素表示的是移动的方向 ![]() ![]() ![]() ![]() ![]() ![]() main.cpp 代码语言:javascript复制#include #include #include using namespace std; #include"stack.hpp" #define M 4 #define N 4 //迷宫 maze[M+2][N+2] int maze[M + 2][N + 2] = { {1, 1, 1, 1, 1, 1}, { 1,0,0,1,1,1 }, { 1,0,0,0,0,1 }, { 1,0,1,1,1,1 }, { 1,0,0,0,0,1 }, { 1,1,1,1,1,1 }, }; //用来记录走迷宫顺序的结构体 typedef struct { //int cx,int cy表示x和y方向的增量 //cy+1:表示向右走 cy-1:向左走 //cx+1:表示向下走 cx-1:向上走 int cx, cy; }Direction; //数组中方向村粗顺序:右下左上 Direction direct[4] = { {0,1},{1,0},{0,-1},{-1,0} }; //用来记录当前位置,然后压入栈中 typedef struct { int x, y;//记录当前位置的坐标 int di;//记录当前位置下一次移动的方向 }Box; //判断是否走出迷宫的代码 //参数1:迷宫图 参数2:存放方向的数组 参数3:保存通路的栈 bool findPath(int maze[M + 2][N + 2], Direction direct[], LinkStack& s) { //创建Box temp结构体来保存当前位置 Box temp; //记录当前位置和方向 int x=0, y=0, di=0; //记录下次移动的位置坐标 int line=0, col=0; //一开始点位于迷宫maze[1][1]的位置,所以将该位置的值变为-1 maze[1][1] = -1; //temp值记录当前位置,将di设置为-1 temp = { 1,1,-1 }; //将temp记录的当前位置压入栈中 s.push(temp); //进入外层循环 while (!s.isEmpty())//栈不为空 { //弹出栈顶元素 temp = s.pop(); //更新当前位置 x = temp.x; y = temp.y; di = temp.di+1; //内层循环 while (di < 4)//尝试四个方向 { //更新下一次移动的位置坐标 line = x+direct[di].cx; col = y+direct[di].cy; //判断下一个位置能否走 if (maze[line][col] == 0) { //如果下一个位置能够移动,就更新temp存储当前位置的值 temp = { x,y,di }; //将temp结构体存储当前位置的信息压入栈中 s.push(temp); //更新当前位置 x = line; y = col; //当前位置的值改为-1,表示走过了,下次不能走 maze[line][col] = -1; //判断当前位置是否为迷宫出口 if (x == M && y == N) { //把迷宫出口也压入栈中 temp = { x, y, di }; s.push(temp); //找到出口,退出函数 return true; } else { //没有找到出口,但是可以移动到下一个点,那么下一个点起始移动方向更新为右,因为移动方向顺序:右下左上 di = 0; } } else { //比如一开始要往右走:如果右方向不能走,就要改变方向移动 di++; } } } return false; } //测试打印迷宫通路 void test() { LinkStack s; findPath(maze, direct, s); //逆序遍历栈 int i = 0; int num = s.size(); Box* data = new Box[num]; while (!s.isEmpty()) { //头删 data[i++] = s.getTop(); s.pop(); } //对数组进行逆序遍历 for(int j = num-1; j >=0; j--) { cout next; free(temp); } node* top = NULL; } template int LinkStack::size() { //计算链表的长度 return num; }测试结果: ![]() |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |