MyStack-BaseCpp.rar

#include "MyMaze.h" #include"MyStack.h" #include <iostream> using namespace std; //初始化迷宫内各个格子的状态 void Maze_Init(Cell maze[MAZE_SIZE][MAZE_SIZE]) { for (int i = 0; i < MAZE_SIZE; i++) { for (int j = 0; j < MAZE_SIZE; j++) { //横纵坐标 maze[i][j].m_x = i; maze[i][j].m_y = j; //当前状态，WALL还是AVAILABLE if (maze_table[i][j]) { maze[i][j].m_status = WALL; } else { maze[i][j].m_status = AVAILABLE; } //设置进出方向 maze[i][j].m_in = UNKOWN; maze[i][j].m_out = UNKOWN; } } } //获取下一个方向 Dir NextDir(Dir dir) { return Dir(dir + 1); } //根据当前cell的出方向m_out获取邻居 Cell* Neighbor(Cell* cell) { switch (cell->m_out) { case LEFT:return cell-1; break; case RIGHT:return cell + 1; break; case UP:return cell - MAZE_SIZE;; break; case DOWN:return cell + MAZE_SIZE; break; default:cout << "It msut be wrong!\n"; } } //根据当前cell的出方向返回下一cell Cell* Advance(Cell *cell) { Cell* next=cell; switch (cell->m_out) { case LEFT:next = cell - 1; next->m_in = RIGHT; break; case RIGHT:next = cell + 1; next->m_in = LEFT; break; case UP:next = cell - MAZE_SIZE; next->m_in = DOWN; break; case DOWN:next = cell + MAZE_SIZE; next->m_in = UP; break; default:cout << "It msut be wrong!\n"; } return next; } //路径搜索 bool Maze_Route(Cell maze[MAZE_SIZE][MAZE_SIZE], Cell* src, Cell* dst) { if ((AVAILABLE != src->m_status) || (AVAILABLE != dst->m_status)) return false; MyStack<Cell*> path; src->m_in = UNKOWN; src->m_status = ROUTE; //将起始点入栈 path.Push(src); do { Cell* temp_cell = path.Top(); //如果路径栈栈顶与目的地址相同则查找完毕 if (temp_cell == dst) { //更新迷宫内各个格子的状态 int path_size = path.Size(); for (int i = 0; i < path_size; i++) { Cell* cell = path.Pop(); maze[cell->m_x][cell->m_y].m_status = ROUTE; } return true; } //选择一个方向 while (NO_WAY > (temp_cell->m_out = NextDir(temp_cell->m_out))) { //如果选择的方向中有可用的格子，则顺着方向前进1步 if (AVAILABLE == Neighbor(temp_cell)->m_status) break; } //如果上下左右均没有可用的格子 if (NO_WAY <= temp_cell->m_out) { //则标记当前格子为BACKTRACKED //弹出路径栈栈顶原始，回退1步尝试其他方向的路径 temp_cell->m_status = BACKTRACKED; temp_cell = path.Pop(); } else { //如果找到可用的格子，将当前格子压栈并按照选择的方向前进一步 //新格子继续从UNKOWN状态开始寻找下一个可用路径 temp_cell = Advance(temp_cell); temp_cell->m_out = UNKOWN; temp_cell->m_status = ROUTE; path.Push(temp_cell); } } while (!path.IsEmpty()); return false; } //迷宫路径的显示 void Maze_Display(Cell maze[MAZE_SIZE][MAZE_SIZE]) { char ch = 0; for (int i = 0; i < MAZE_SIZE; i++) { for (int j = 0; j < MAZE_SIZE; j++) { if (ROUTE == maze[i][j].m_status) { ch = ROUTE_CH; } else if (WALL == maze[i][j].m_status) { ch = WALL_CH; } else if (BACKTRACKED == maze[i][j].m_status) { ch = 'x'; } else { ch = ' '; } cout << ch; } cout << endl; } }