man = st.gettop(); } else//栈空了 说明回到出口了，此迷宫没有通路 { return false; }
} if(man.di < UP)//curpos点不通，则继续按方向顺序探索man周围的下 一个点 {
st.pop(); man.di = (DIR)(man.di+1); st.push(man); curpos = NextPos(man.pos,man.di); } } } }while(!st.isempty()); return false; }
return ((x==p.x)&&(y==p.y)); } } Pos;
迷宫中人的模拟：
typedef struct Man //模拟人 {
Pos pos; DIR di; } Man;
3.算法设计
系统输出迷宫通路，迷宫在程序中设定。
（1）参数给出当前位置及方向，返回下一位置：
Pos NextPos(Pos pos, DIR di) {
图1 迷宫示意图 迷宫四周设为墙；无填充处，为可通处。设每个点有四个 可通方向，分别为东、南、西、北。左上角为入口。右下角为 出口。迷宫有一个入口，一个出口。设计程序求解迷宫的一条 通路。
2.数据结构设计
栈类的实现：
template<class Type> class Stack { public:
man = st.gettop(); while(man.di==UP && !st.isempty()) {//如果curpos不能通过，且man周围的点都探索完毕，人 就往后退
st.pop(); // MarkMaze(maze,man.pos);
if(!st.isempty()) {
man = st.gettop(); } else//栈空了 说明回到出口了，此迷宫没有通路 {
} void push(Type &x) { if(!isfull()) {
base[top++] = x; } } void pop() { if(!isempty()) { top--; } } Type gettop()const { if(!isempty()) { return base[top-1]; } } private: enum{STACK_SIZE=100}; Type *base; size_t top; size_t capacity; };
} while(!st.isempty()); return false; }
（2） 迷宫通路的输出在模拟走迷宫中实现，与迷宫通路的标 记同时完成：
void FootMaze(Maze maze,Pos pos) {
maze[pos.x][pos.y] = 2; cout <<"("<<pos.x<<","<<pos.y<<") "; }
bool PassMaze(Maze maze,Pos start, Pos end) { Man man; //pos di Stack<Man> st; Pos curpos = start; do//重复探索 直至curpos==end找到出口，或者栈变空（没有任何一条通
路） { if(Pass(maze,curpos))//如果当前点curpos能通过 则将man的位置标记到 此点，设置默认探索方向从RIGH开始 {
7.源码
#include <iostream> #include <string>
using namespace std;
template<class Type> class Stack { public: Stack() { capacity = STACK_SIZE; base = new Type[capacity]; top = 0; } ~Stack() { capacity = 0; delete []base; base = NULL; top = 0; } public: bool isfull()const { return top >= capacity; } bool isempty()const { return top == 0;
int main() { Pos start = {0,1}; Pos end = {9,8}; Maze maze = { {1,0,1,1,1,1,1,1,1,1}, {1,0,1,1,1,1,0,0,0,1}, {1,0,1,1,1,1,0,1,1,1}, {1,0,1,0,0,0,0,0,0,1}, {1,0,0,0,1,1,0,1,0,1}, {1,1,1,1,1,1,0,1,0,1}, {1,1,0,0,0,0,0,0,0,1}, {1,1,1,1,1,0,1,1,0,1}, {1,1,1,0,0,0,0,1,0,1}, {1,1,1,1,1,1,0,0,0,1} }; ShowMaze(maze); if(!PassMaze(maze,start,end)) { cout<<"没有出路！"<<endl; return 0; } cout<<"-------------------"<<endl; ShowMaze(maze);
man.pos = curpos; man.di = RIGHT; //默认从RIGHT开始探索 FootMaze(maze,man.pos); if(curpos == end) return true; st.push(man); curpos = NextPos(man.pos,man.di); } else { if(!st.isempty()) { man = st.gettop(); while(man.di==UP && !st.isempty())//如果curpos不能通过，且man周围 的点都探索完毕，人就往后退 { st.pop(); // MarkMaze(maze,man.pos); if(!st.isempty()) {
return false; }
} if(man.di < UP)//curpos点不通，则继续按方向顺序探索 man周围的下一个点 {
st.pop(); man.di = (DIR)(man.di+1); st.push(man); curpos = NextPos(man.pos,man.di); } } }
switch(di) { case RIGHT:
pos.y += 1; break; case DOWN: pos.x += 1; break; case LEFT: pos.y -= 1; break; case UP: pos.x -= 1; break; } return pos; }
（2）迷宫求解：
bool PassMaze(Maze maze,Pos start, Pos end) {
Man man; //pos di Stack<Man> st; Pos curpos = start; do//重复探索 直至curpos==end找到出口，或者栈变空（没有任何 一条通路） {
if(Pass(maze,curpos))//如果当前点curpos能通过 则将man的位置 标记到此点，设置默认探索方向从RIGH开始
return top >= capacity; } bool isempty()const {
return top == 0; } void push(Type &x) {
if(!isfull()) {
base[top++] = x; } } void pop() { if(!isempty()) {
Pos NextPos(Pos pos, DIR di) { switch(di) { case RIGHT: pos.y += 1; break; case DOWN: pos.x += 1; break; case LEFT: pos.y -= 1; break; case UP: pos.x -= 1; break; } return pos; }
///////////////////////////////////////////// #define ROW 10 #define COL 10
typedef enum { RIGHT=1,
DOWN, LEFT, UP, }DIR;
typedef int Maze[ROW][COL];//10x10的二维数组 模拟迷宫 //表示位置 typedef struct Pos { int x; int y; bool operator==(const Pos &p) { return ((x==p.x)&&(y==p.y)); } }Pos; //模拟人 typedef struct Man { Pos pos; DIR di; }Man;
void ShowMaze(Maze maze) { for(int i=0; i<10; ++i) { for(int j=0; j<10; ++j) {
cout<<maze[i][j]<<" "; } cout<<endl; } }
bool Pass(Maze maze, Pos pos) { return maze[pos.x][pos.y] == 0; } //将能走通的位置标记为2 void FootMaze(Maze maze,Pos pos) { maze[pos.x][pos.y] = 2; }