程序员做网站,南安网站开发,wordpress 优酷去广告插件,中国制造app上篇文章写出了利用函数形成栈桢的特性完成迷宫求解问题, 本篇文章我们自己手动维护一个栈, 其进行出栈, 入栈, 取栈顶元素, 来完成迷宫求解寻路的过程 思路和以前一样, 首先, 我们先定义一个栈, 对其初始化, 同时, 定义一个迷宫地图, 对该地图进行初始化, 先判断当前… 上篇文章写出了利用函数形成栈桢的特性完成迷宫求解问题, 本篇文章我们自己手动维护一个栈, 其进行出栈, 入栈, 取栈顶元素, 来完成迷宫求解寻路的过程 思路和以前一样, 首先, 我们先定义一个栈, 对其初始化, 同时, 定义一个迷宫地图, 对该地图进行初始化, 先判断当前位置是否可以落脚, 如果不能落脚就直接 return, 如果能够落脚, 就将入栈同时将其标记, 标记完之后就循环取栈顶元素, 直到取栈顶元素失败时回溯, 每取一个栈顶元素就判断一下该栈顶元素是否是出口, 如果是出口, 就说明迷宫探测完毕, 如果不是出口,就按顺序(顺时针)探测该点四周的点, 判断该位置是否可以落脚, 能落脚就将其标记, 然后将其入栈,然后进入下以次循环, 如果四周的点都探测完毕, 此时就可以回溯了(出栈)
void GetPathByLoop(Maze* maze, Point entry)
{if(maze NULL){return;//非法输入}if(entry.row 0 || entry.row MAX_ROW || entry.col 0 || entry.col MAX_COL){return;//非法输入}//创建栈, 并且初始化, 保存走过的路径SeqStack stack;SeqStackInit(stack);//判断入口点是否可以落脚, 能落脚就将其入栈if(!CanStay(maze, entry)){return;}SeqStackPush(stack, entry);//循环获取当前栈的栈顶元素, (栈顶元素一定可以落脚)栈为空时回溯结束//判断是否为出口, 是的话就退出while(1){Point cur;int ret SeqStackGetFront(stack, cur);if(ret 0){return;}if(IsExit(maze, cur, entry)){printf(找到了一条路\n);return;}printf((%d, %d)\n, cur.row, cur.col);//按顺序取相邻元素判断是否可以落脚, 能落脚就标记入栈, 进入下一轮循环Point up cur;up.row - 1;if(CanStay(maze, up)){Mark(maze, up);SeqStackPush(stack, up);continue;}Point right cur;right.col 1;if(CanStay(maze, right)){Mark(maze, right);SeqStackPush(stack, right);continue;}Point down cur;down.row 1;if(CanStay(maze, down)){Mark(maze, down);SeqStackPush(stack, down);continue;}Point left cur;left.col - 1;if(CanStay(maze, left)){Mark(maze, left);SeqStackPush(stack, left);continue;}//如果四个元素都不能落脚, 就出栈SeqStackPop(stack);//判断当前是否可以落脚}
}
