首页 > 代码库 > 利用数据结构栈求解迷宫问题
利用数据结构栈求解迷宫问题
本段程序主要利用数据结构栈的先进后出特点,实现回溯求解迷宫路径问题。
#include<iostream> #include<stack> using namespace std; //坐标类 struct Point { int x; int y; }; //地图类 template<int A> struct Map { int (*p)[A]; int row;//行数 int col;//列数 }; //start起始点, end终止点 template<int A> bool FindPath(Map<A> & map,Point & start,Point & end) { //先给图的外围加上障碍 for(int i = 0;i<=map.col;i++) { map.p[0][i] = map.p[map.row][i] = 1; } for(int i = 0;i<=map.row;i++) { map.p[i][0] = map.p[i][map.col] = 1; } //用于保存路径的栈 stack<Point> stackpath; //用于方向选择的偏移量数组 按照顺时针的方向 Point offset[4]; offset[0].x = 0; offset[0].y = 1;//向右 offset[1].x = 1; offset[1].y = 0;//向下 offset[2].x = 0; offset[2].y = -1;//向左 offset[3].x = -1; offset[3].y = 0;//向上 //将起点初始化为障碍点 map.p[start.x][start.y] = 1; //起点入栈 stackpath.push(start); //用于下一步方向选择的变量 int option = 0; //下一步的最大选择变量 int MaxOption = 3; // while((start.x != end.x)||(start.y != end.y)) { //选择下一步 while(option<=MaxOption) { int x = start.x + offset[option].x; int y = start.y + offset[option].y; if(map.p[x][y]!=1) { start.x = x; start.y = y; break; } option++; } //如找到了下一点 if(option<=MaxOption) { //入栈 stackpath.push(start); //设置障碍 map.p[start.x][start.y] = 1; option = 0; } else//没找到了下一点 { //向后退一步,出栈 stackpath.pop(); //消除入栈时设置的障碍 map.p[start.x][start.y] = 0; if(stackpath.empty()) { return false; } //设置回溯后的option if(start.x == stackpath.top().x) { if((start.y - stackpath.top().y)==1)//向右 { option = 0; } if((start.y - stackpath.top().y)==-1)//向左 { option = 2; } } if(start.y == stackpath.top().y) { if((start.x - stackpath.top().x)==1)//向下 { option = 1; } if((start.x - stackpath.top().x)==-1)//向上 { option = 3; } } option++; start.x = stackpath.top().x; start.y = stackpath.top().y; } } //找到路径,并输出stackpath while(!stackpath.empty()) { cout<<"<"<<stackpath.top().x<<","<<stackpath.top().y<<">"<<endl; stackpath.pop(); } return true; } int main() { //建立迷宫 Map<10> map; map.col = map.row = 9; int p[10][10]; for(int i =0;i<10;i++)//初始化迷宫 { for(int j=0;j<10;j++) { p[i][j] = 0; } } //为迷宫设置障碍 p[1][3] = 1;p[1][7] = 1;p[2][3] = 1;p[2][7] = 1; p[3][5] = 1;p[3][6] = 1;p[4][2] = 1;p[4][3] = 1; p[4][4] = 1;p[5][4] = 1;p[6][2] = 1;p[6][6] = 1; p[7][2] = 1;p[7][3] = 1;p[7][4] = 1;p[7][6] = 1; p[8][1] = 1; map.p = p; Point start,end; start.x = start.y = 1; end.x =8,end.y = 8; if(!FindPath<10>(map,start,end)) { cout<<"该迷宫无解!"<<endl; } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。