#include<iostream>
using namespace std;
#include<iomanip>
class Position//位置类（栈数据元素类）
{
public:
int x;//存X坐标
int y;//存Y坐标
};
class Stacknode//栈结点类
{
public:
Position data;
Stacknode *next;
};
class Stack//栈类
{
public:
Stacknode *top;//栈顶指针
Stacknode *base;//栈底指针
unsigned height;//栈高
Stack()//无参构造函数
{
top=NULL;
height=0;
base=NULL;
}
~Stack()//析构函数
{
Clear();
}
void Clear()
{
Position po;
Pop(po);
}//清空当前栈中元素
void Push(Position
&);//进栈函数
void Pop(Position &);//出栈函数
};
void Stack::Push(Position &po)
{
Stacknode *p;
if(top)//若栈非空
{
p=new Stacknode;
p->data=po;
p->next=top;//将结点插入链式栈前端，成为栈顶元素
top=p; //修改栈顶指针
}
else//若为空栈
{
top=new Stacknode; //为栈顶元素分配内存
//将x赋给栈顶数据元素
top->data=po;
top->next=NULL;
}
height++;
}
void Stack::Pop(Position &po)
{
Stacknode *p;
if(height)//若栈中有元素
{
po=top->data;
cout<<"("<<po.x<<","<<po.y<<") ";
p=top;//将栈顶指针赋给p
top=top->next;//修改栈顶指针,下移一个位置
delete p;//删除原栈顶结点
height--;//栈高减1
}
else
return;
}
class Maze
{
public:
int m,n,maze[8][8];
void Getnum()//获取迷宫的行数和列数
{
m=8;
n=8;
}
void Getmaze();//构造和输入迷宫，为迷宫四周加上围栏
void Simplemaze();//简化迷宫
void Putmaze();//输出迷宫
void compare(Stack &s,int i,int j);
};
void Maze::Getmaze()//构造和输入迷宫，为迷宫四周加上围栏
{
int i,j;
for (j=0;j<8;j++)
{
maze[0][j]=1;
}
for (j=0;j<8;j++)
{
maze[7][j]=1;
}
for (i=0;i<8;i++)
{
maze[i][0]=1;
}
for (i=0;i<8;i++)
{
maze[i][7]=1;
}
cout<<"请输入迷宫的形状："<<endl;
for(i=1;i<7;i++)
{
for(j=1;j<7;j++)
{
cin>>maze[i][j];
}
}
}
void Maze::Simplemaze()//简化迷宫
{
for (int t=1;t<7;t++)
{
for (int r=1;r<7;r++)
{
if (maze[t-1][r]+maze[t+1][r]>=3)
maze[t][r]=1;
}
}
maze[1][1]=0;
maze[6][7]=4;
}
void Maze::Putmaze()//输出迷宫
{
for(int i=0;i<8;i++)
{
for(int j=0;j<8;j++)
{
cout<<setw(5)<<maze[i][j];
}
cout<<endl;
}
}
void Maze::compare(Stack &s,int i,int j)
{
int p=0,q=0,d;
Position point;
if(maze[i][j]==4)
{
cout<<"恭喜，该迷宫可以走出！"<<"具体步骤如下"<<endl;
/*
while(s.base!=s.top) //输出栈中的所有元素
{
p=s.base->data.x;
q=s.base->data.y;
s.base++;
cout<<"("<<p<<","<<q<<")"<<" ";
}
*/
s.Pop(point);
return ;
}
if(maze[i][j]==2||maze[i][j]==1)
{
cout<<"迷宫不能走出\n";
return;
}
if(maze[i][j]==0)
{
maze[i][j]=2;
system("cls");
Putmaze();
point.x=i;
point.y=j;
s.Push(point);
cout<<"请输入方向:1表示向右,2表示向下,3表示向左,4表示向上:";
cin>>d;
switch (d)
{
case 2:
compare(s,i+1,j); break;
case 1:
compare(s,i,j+1);break;
case 4:
compare(s,i-1,j);break;
case 3:
compare(s,i,j-1);break;
}
return;
}
}
int main()
{
Stack s;
Maze MAZE;
int m,n;
MAZE.Getnum();
m=MAZE.m;
n=MAZE.n;
MAZE.Getmaze();
MAZE.Simplemaze();
MAZE.Putmaze();
MAZE.compare(s,1,1);
return 0;
}
