lady.cpp

利用堆栈实现老鼠迷宫问题,寻找出迷宫的路径

#include"lady.h"
#include<stack>
#include<process.h>
#include <stdio.h>
#include<time.h>

#include<iostream>

using namespace std;

stack<int> route_x ;
stack<int> route_y ;

stack<int> list_x;
stack<int> list_y;

lady::lady()
{	
    int n,i,j;
    for(i=0;i<=N+1;i++)
		for(j=0;j<=M+1;j++)
			lad[i][j]=1;

    srand((unsigned)time(NULL));                 //随机函数初始

    for(i=1;i<=N;i++) 
		for(j=1;j<=M;j++)
		{
			n=rand()%16;                            //随机函数
			if(n<N && n<M) lad[i][j]=0;
		}
                                                  //给迷宫留入口
	lad[1][1]=2;
	lad[1][2]=0;
	lad[1][3]=0;
	lad[N-1][M-1]=0;                                  //给迷宫留出口
	lad[N-2][M-1]=0;
	lad[N-2][M-2]=0;
	lad[N-3][M-2]=0;
}

lady::~lady()
{

}

bool can_be_left=true;
bool can_be_right=true;
bool can_be_up=true;
bool can_be_down=true;
int x=1;
int y=1;
int cx=1;
int cy=1;

void lady::move()
{
	if(lad[N][M]==2) 
	{
		cout<<"成功啦~~ !"<<endl<<endl;
		print_route();
	}                   //GAME OVER

	else if(lad[x+1][y]==0 &&  can_be_right==true)  //RIGHT
	{
		lad[x+1][y]=2;
		lad[x][y]=0;
		x=x+1;   y=y;
		route_x.push(x);
		route_y.push(y);
		bool can_be_left=false;
		bool can_be_right=true;
		bool can_be_up=true;
		bool can_be_down=true;
		print_lad();
		move();
	}

	else if(lad[x][y+1]==0 &&  can_be_down==true)    //DOWN
	{
		lad[x][y+1]=2;
		lad[x][y]=0;
		x=x;   y=y+1;
		route_x.push(x);
		route_y.push(y);
		can_be_up=false;
		can_be_right=true;
		can_be_left=true;
		can_be_down=true;
		print_lad();
		move();
	}

	else if(lad[x][y-1]==0 &&  can_be_up==true)    //UP
	{
		lad[x][y-1]=2;
		lad[x][y]=0;
		x=x+1;   y=y;
		route_x.push(x);
		route_y.push(y);
		can_be_down=false;
		can_be_right=true;
		can_be_left=true;
		can_be_up=true;
		print_lad();
		move();
	}

	else if(lad[x-1][y]==0 &&  can_be_left==true)   //left
	{
		lad[x-1][y]=2;
		lad[x][y]=0;
		x=x-1;   y=y;
		route_x.push(x);
		route_y.push(y);
		can_be_right=false;
		can_be_up=true;
		can_be_left=true;
		can_be_down=true;
		print_lad();
		move();
	}

	else if (!route_x.empty())   
	{
		route_x.pop();
		route_y.pop();
		cx=route_x.top;
		cy=route_y.top;

		if ((cx==x-1) && (cy==y))				//left
		{
			lad[x][y]=0;
			lad[cx][cy]=2;
			x=cx;   y=cy; 
			can_be_right=false;
			can_be_up=true;
			can_be_left=true;
			can_be_down=true;
			print_lad();
			move();
		}

		else if ((cx==x) && (cy==y-1))				//up
		{
			lad[x][y]=0;
			lad[cx][cy]=2;
			x=cx;   y=cy; 
			can_be_right=true;
			can_be_up=true;
			can_be_left=true;
			can_be_down=false;
			print_lad();
			move();
		}
		
		else if ((cx==x) && (cy==y+1))				//down
		{
			lad[x][y]=0;
			lad[cx][cy]=2;
			x=cx;   y=cy; 
			can_be_up=false;
			can_be_right=true;
			can_be_left=true;
			can_be_down=true;
			print_lad();
			move();
		}

		else if ((cx==x+1) && (cy==y))				//right
		{	
			lad[x][y]=0;
			lad[cx][cy]=2;
			x=cx;   y=cy; 
			can_be_left=false;
			can_be_up=true;
			can_be_right=true;
			can_be_down=true;
			print_lad();

			move();
		}
		else cout<<endl<<endl<<"迷宫没有出口!!"<<endl;
	}
}

void lady::print_lad()
{
    system("cls.exe"); 

	cout<<endl<<endl<<"迷宫:"<<endl<<"1.使用随机数生成迷宫"<<endl;
	cout<<"表示物：▅--障碍物   @@--老鼠  "<<endl<<endl;

	for(int i=0;i<=N+1;i++)
	{
		for(int j=0;j<=M+1;j++)
		{
			if(lad[i][j]==1) cout<<"▅";
			else if(lad[i][j]==0) cout<<"  ";
			else if(lad[i][j]==2) cout<<"@@";
		}
		cout<<endl;
	}
}

void lady::print_route()
{	
	int px; int py;

	cout<<"最捷路径:"<<endl<<endl;;

	while(!(route_x.empty()))
	{	px=route_x.top();   py=route_y.top();
		route_x.pop();      route_y.pop();
		list_x.push(px);	list_y.push(py);
	}

	while(!(list_x.empty()))
	{
		px=list_x.top();	  py=list_y.top();
		list_x.pop();		  list_y.pop();
		cout<<"( "<<px<<","<<py<<" )"<<" ==> ";
	}	
}