#include<iostream>
#include<ctime>
#include<stack>
#include<windows.h>
using namespace std;

const int East = 0;
const int South = 1;
const int West = 2;
const int North = 3;
const int pause = 50; //老鼠走一步需要的毫秒数
class MouseMaze
{
public:
MouseMaze(int h, int w);
~MouseMaze();
void display()const;
bool hasCrossOver();

private:
const int row;
const int col;
char **p;
void Init();
};

MouseMaze::MouseMaze(int h, int w):row(h), col(w){
p = new char *[row];
for (int i=0; i<row; ++i)
p[i] = new char[col];
Init();
}

MouseMaze::~MouseMaze(){
for (int i=0; i<row; i++)
delete[] p[i];
delete[] p;
}

void MouseMaze::display()const {
for (int i=0; i<row; ++i){
for (int j=0; j<col; ++j)
cout << p[i][j];
cout << endl;
}
}

void MouseMaze::Init() //随机生成迷宫
{
srand(time(0));
for (int i=0; i<row; ++i){
for (int j=0; j<col; ++j)
{
if ((i==0) || (j==0) || (i==row-1) || (j==col-1)) {
p[i][j] = '*';
continue;
}
if (rand() % 100 < 80)
p[i][j] = ' ';
else
p[i][j] = 'O';
}
}
p[1][1] = 'Z';
p[row-2][col-1] = ' '; //出口
}

bool MouseMaze::hasCrossOver(){
int flag, i = 1, j = 1;
stack<int> s;
while (true){
if (i==row-2 && j==col-1)
{
int m, n;
stack<int> newStack;
while (!s.empty()){
newStack.push(s.top());
s.pop();
}
for (m=0; m<row; ++m){
for (n=0; n<col; ++n)
if (p[m][n] == 'Z')
p[m][n] = ' ';
}
m = 1;
n = 1;
p[m][n] = 'Z';
while (!newStack.empty()){
flag = newStack.top();
switch (flag)
{
case East:
++n; break;
case South:
++m; break;
case West:
--n; break;
case North:
--m; break;
}
p[m][n] = 'Z';
Sleep(pause);
system("cls");
display();
newStack.pop();
}
return true;
}//end if;

if ((j+1 < col) && (p[i][j+1] == ' ')){ //East
p[i][++j] = 'Z';
s.push(East);
}
else if ((i+1 < row) && (p[i+1][j] == ' ')){//South
p[++i][j] = 'Z';
s.push(South);
}
else if ((j-1 > 0) && (p[i][j-1] == ' ')){ //West
p[i][--j] = 'Z';
s.push(West);
}
else if ((i-1 > 0) && (p[i-1][j] == ' ')){ //North
p[--i][j] = 'Z';
s.push(North);
}
else
{
if (s.empty()) return false;
flag = s.top();
s.pop();
switch (flag)
{
case East:
--j; break;
case South:
--i; break;
case West:
++j; break;
case North:
++i; break;
}
}
}
}

void main()
{
MouseMaze gMaze(20, 79); //迷宫高20， 宽79
gMaze.display();
system("pause");
if (gMaze.hasCrossOver())
cout << "\n哈哈，老鼠成功逃出迷宫了~~~~" << endl;
else
cout << "\n可怜的老鼠，这辈子别想逃走!!!" << endl;
}

//我是通过不断的清屏才能动态显示老鼠的当前位置，画面闪烁得厉害，有什么办法！