#includeusing namespace std;//=======================================位置(坐标)类========================class Coordinate{ friend class Node; friend class LinkStack; friend bool mazePath(char **maze, int m);//迷宫路径 public: Coordinate(); int row; int col;}; //=======================================链栈的结点类========================class Node{ friend class LinkStack; public: Node(); Coordinate data; Node *next;};//=======================================链栈类================================class LinkStack{ friend bool mazePath(char **maze,int m); public: void Recursion(Node *p);//递归函数 void PrintStack(LinkStack &L); bool Empty(LinkStack &L); Coordinate DeleteStack(LinkStack &L); void AddStack(LinkStack &L,Coordinate N); LinkStack(); private: Node *top;};//========================================位置类的初始化函数====================Coordinate::Coordinate(){ row = 1; col = 1;}//=======================================结点类的初始化函数===================== Node::Node(){ next = NULL;}//=========================================堆栈类的初始化函数===================LinkStack::LinkStack(){ top = NULL;}//===========================================入栈===============================void LinkStack::AddStack(LinkStack &L,Coordinate N){ Node *p = new Node; p->data = N; p->next = L.top; L.top = p;}//==========================================出栈================================Coordinate LinkStack::DeleteStack(LinkStack &L){ Node *p = L.top; Coordinate N = top->data; L.top = p->next; delete p; return N;}//=========================================判断栈是否为空=======================bool LinkStack::Empty(LinkStack &L){ return (top = NULL) ? 1:0;}//=========================================递归输出栈的内容=====================void LinkStack::PrintStack(LinkStack &L){ Node *p = new Node; p = L.top; LinkStack::Recursion(p); cout << '(' << p->data.row << ',' << p->data.col << ')' << "--->";}//=========================================递归函数=============================void LinkStack::Recursion(Node *p){ if(p->next) { p = p->next; LinkStack::Recursion(p); cout << '(' << p->data.row << ',' << p->data.col << ')' << "--->"; }}//=============实现迷宫算法,返回值为是否到达迷宫出口的布尔值====================bool mazePath(char maze[7][7], int m){ LinkStack path; //初始化偏移变量 Coordinate move[4]; move[0].row = 0;move[0].col = 1;//向右移动 move[1].row = 1;move[1].col = 0;//向下移动 move[2].row = 0;move[2].col = -1;//向左移动 move[3].row = -1;move[3].col = 0;// 向上移动 //像迷宫周围增加一圈障碍物 for(int i = 0;i <= m + 1;i ++) { maze[i][0] = maze[i][m + 1] = '#'; //左和右 maze[0][i] = maze[m + 1][i] = '#'; //上和下 } Coordinate now; now.row = 1; now.col = 1; maze[1][1] = 'x'; //阻止返回入口 int choose = 0; int lastchoose = 3; //搜索一条路径 while(now.row != m || now.col != m) { int newr,newc; while(choose <= lastchoose)//依次选择路径 { newr = now.row + move[choose].row; newc = now.col + move[choose].col; if(maze[newr][newc] == '0') { break; } choose ++; //进行下一次选择 } if(choose <= lastchoose) { //若找到相邻位置则移动到maze[newr][newc] path.AddStack(path,now); now.row = newr; now.col = newc; maze[newr][newc] = 'x';//设置障碍物,以阻止再次访问 choose = 0; } else //如果没有找到相邻位置则回溯 { if(path.Empty(path)) { return false; } Coordinate Next;//Next用来存放四周都没有通路的这个结点的上一个结点, //注意next的下一个结点就是now,可是这个now已经没有路可走了, //所以就只能在next后面再取一个路实验,看新取得的路有没有通路 Next = path.DeleteStack(path);//将这个结点删除,把该结点的值赋给Next, //注意此时now是next取的用来探路的点,可是此时now无路可走 //本实验用来搜寻有没有路的顺序依次是右下左上 if(now.col - Next.col == 1 && now.row - Next.row == 0)//如果now 在 Next的右边 { choose = 1; } else if(now.col - Next.col == 0 && now.row - Next.row == 1)//如果 row 在 Next 的下面 { choose = 2; } else if(now.col - Next.col == -1 && now.row - Next.row == 0)//如果 row 在 Next 的下面 { choose = 3; } else if(now.col - Next.col == 0 && now.row - Next.row == -1)//如果row 在 Next 的上面 { choose = 4;//设置为大于3的数,说明Next该点周围都没有通路,再进行递归的话,就会重新在退一个位置进行判断 } now = Next; } } //显示迷宫地图 cout << "迷宫地图:" << '\n' << endl; for(int col = 0;col < 7;col++) { cout << '\t' << col << "列"; } cout << '\n'; for(int mi = 0;mi < 7;mi++) { cout << mi << "行"; for(int mj = 0;mj < 7;mj++) { cout << '\t' << maze[mi][mj]; } cout << '\n' << '\n'; } cout << '\n'; cout << "迷宫路径:" << '\n' << endl; path.PrintStack(path); cout << '(' << m << ',' << m << ')' << '\n' << '\n'; return true; //到达迷宫出口} //======================主函数,调用mazePath()函数===============================int main(){ int m = 5; char maze[7][7]; //初始化迷宫数组 for(int i = 1;i <= m;i ++) { for(int j = 1;j <= m;j ++) { maze[i][j] = '0'; } } //设置迷宫 maze[1][2] = '#'; maze[2][2] = '#'; maze[2][4] = '#'; maze[2][5] = '#'; maze[3][4] = '#'; maze[4][2] = '#'; maze[5][2] = '#'; maze[5][4] = '#'; mazePath(maze,m); system("pause"); return 0;}