typedef struct { int x; int y;}Pos;//迷宮類型typedef struct { int square[10][10] =  {{1,1,1,1,1,1,1,1,1,1},{1,0,0,0,0,0,0,0,0,1},{1,1,1,1,0,1,1,1,0,1},{1,0,0,0,0,1,0,1,0,1},{1,0,1,1,1,1,0,1,1,1},{1,0,0,0,0,1,0,0,0,1},{1,0,1,1,0,0,0,1,0,1},{1,0,1,1,1,0,1,1,1,1},{1,0,0,0,1,0,0,0,0,1},{1,1,1,1,1,1,1,1,1,1}, };}Maze;typedef Pos SElemType;

//順序棧#define MAXSIZE 50typedef struct { SElemType *base; SElemType *top;  //棧頂指針 int stacksize;}SqStack;

typedef int Status;#define OK 1;#define ERROR 0;//棧的相關操作//初始化棧Status initStack(SqStack &s);//壓棧Status push(SqStack &s, SElemType e);//出棧SElemType pop(SqStack &s);//清空棧Status clearStack(SqStack &s);//摧毀棧void destroyStack(SqStack &s);//遍歷棧Status stackTravel(SqStack s);

//初始化迷宮(同時生成起始點和終點)void initMaze(Maze &maze);//打印迷宮void showMaze(Maze maze);//尋找出路；傳入一個迷宮和棧找出出路void findWay(Maze &maze,SqStack &s);//判斷該點的四個方向是否有通路，有就前進Pos isExit(Pos p, Maze maze);

#include "pch.h"#include <iostream>#include<time.h>#include<stdlib.h>using namespace std;

//構造空棧Status initStack(SqStack &s) { s.base = new SElemType[MAXSIZE]; if (!s.base) { exit(OVERFLOW);//分配失敗 } s.top = s.base; s.stacksize = MAXSIZE; return OK;}//入棧Status push(SqStack &s, SElemType e) { //判斷棧滿 if (s.top-s.base == s.stacksize) { return ERROR; } //存入元素,*為取指針的值 s.top++; *s.top = e; return OK;}//出棧,用e返回棧頂值SElemType pop(SqStack &s) { SElemType e; //判斷棧為空 if (s.top == s.base) { //若為空則返回一個（-1，-1）的點，判斷由外部調用時進行 e.x = -1; e.y = -1; return e; } e = *s.top; s.top--; return e;}Status clearStack(SqStack &s) { s.top = s.base; return OK;}void destroyStack(SqStack &s) { s.top = NULL; s.stacksize = 0; free(s.base);}Status stackTravel(SqStack s) { while (s.top != s.base) { s.base++; Pos p = *s.base; //輸出走過的路徑 cout <<"("<<p.x<<","<<p.y<<")"<< "-->"; if ( p.x == 0 || p.y == 0|| p.x == 9 ||p.y == 9) { //終點輸出為“End”  cout << "End"; } } cout << endl; return 0;}

///////////////////////////////////////迷宮操作//////////////////////////////////初始化函數，傳入一個迷宮，隨機生成起點和終點，由于起點有一定限制，所以這里起點也固定為幾個最合適的點void initMaze(Maze &maze) { //生成隨機數 srand((unsigned)time(NULL)); int index = rand() % 36 + 1; int start = index % 6 + 1; //生成起始點數值為‘s' switch (start) { case 1: maze.square[1][1] = 's'; break; case 2: maze.square[3][8] = 's'; break; case 3: maze.square[3][6] = 's'; break; case 4: maze.square[6][8] = 's'; break; case 5: maze.square[8][3] = 's'; break; case 6: maze.square[8][8] = 's'; break; } //隨機生成終點'e'表示 while (index = rand()%36+1) { //出口在頂部 if (index >1 &&index<10 && maze.square[1][index-1]!='s') {  maze.square[0][index-1] = 'e';  break; } //出口在右側 else if (index>10 &&index <19) {  if (maze.square[index-10][8] != 1 && maze.square[index-10][8]!='s') {  maze.square[index-10][9] = 'e';  break;  } } //底部出口 else if (index >19&&index<28) {  if (maze.square[8][index - 19] != 's' && maze.square[8][index - 19] != 1) {  maze.square[9][index - 19] = 'e';  break;  } } //左側出口 else if (index >28 && index <=36) {  if (maze.square[index-28][1] != 1 &&maze.square[index-28][1] != 's')  {  maze.square[index - 28][0] = 'e';  break;  } } }}void showMaze(Maze maze) { for (int i = 0; i < 10; i++) { for (int j = 0; j < 10; j++) {  if (maze.square[i][j] == 1)  {  cout << "* ";  }  else if (maze.square[i][j] == 0)  {  cout << " ";  }  else  {  cout << (char)maze.square[i][j]<<" ";  } } cout << endl; }}//尋找迷宮路徑void findWay(Maze &maze,SqStack &s) {//首先遍歷找出起始點和終點并保存下來 Pos start,end; for (int i = 0; i < 10; i++) { for (int j = 0; j < 10; j++) {  if (maze.square[i][j] == 's')  { //起點壓入棧內  start.x = i;  start.y = j;  push(s, start);  }  else if (maze.square[i][j] == 'e')  { //出口  end.x = i;  end.y = j;  } } } //尋找路徑 Pos go = start; //直到找到出口才結束 while ( s.top->x != end.x || s.top->y != end.y) { //獲得下一步坐標 Pos path = isExit(go, maze); if (path.x != go.x || path.y != go.y) {  //前進  maze.square[path.x][path.y] = 'p';  push(s, path);  go = path; } //如果所有放向都走不通（即返回的點是傳入的點），則將其標為“@”，出棧到上一個點，繼續判斷 else {  //走不通pop  maze.square[path.x][path.y] = '@';  pop(s);  go = *s.top; } } maze.square[end.x][end.y] = 'e';}//判斷返回下一步路徑（順序：右下左上），傳入所處位置，從右邊開始判斷是否又通路或者出口，有就返回哪個方向上的點Pos isExit(Pos p,Maze maze) { Pos tempP = p;if (maze.square[tempP.x][tempP.y+1] == 0 || maze.square[tempP.x][tempP.y + 1] == 'e') { tempP.y++; } else if(maze.square[tempP.x+1][tempP.y] == 0 || maze.square[tempP.x +1][tempP.y] == 'e') { tempP.x++; } else if (maze.square[tempP.x][tempP.y - 1] == 0 || maze.square[tempP.x][tempP.y - 1] == 'e') { tempP.y--; } else if (maze.square[tempP.x - 1][tempP.y] == 0 || maze.square[tempP.x - 1][tempP.y] == 'e') { tempP.x--; } return tempP;}

int main(){ while (true) { //創建一個迷宮 Maze maze; initMaze(maze); //初始化一個棧 SqStack S; initStack(S); cout << "*****************************" << endl; cout << "* 1、生成迷宮  2、退出 *" << endl; cout << "*****************************" << endl; cout << "請輸入你的選擇："; int select = 0; cin >> select; if (select == 1) {  cout << "生成隨機起點和出口迷宮：" << endl;  showMaze(maze);  cout << "生成迷宮路徑：" << endl;  findWay(maze, S);  stackTravel(S);  showMaze(maze);  cout << endl; } if (select == 2) {  clearStack(S);  break; } } return 0;}