maze.cpp

迷宫游戏的手动操作

//---------------------------------------------------------------------------------
//								迷宫原型系统 Ver 1.0
//
//														By DingRui
//
//		程序说明：#(0)代表墙，空白(1)代表路，*(2)代表最短路，-(3)代表走过的路
//
//      代码声明：本程序代码算法参考于数据结构书P51页的算法模型
//---------------------------------------------------------------------------------
#define OK 1
#define ERROR 0
#define NULL 0
#define TRUE 1
#define FALSE 0
#define OVERFLOW -2
#define INFEASIBLE -1
#define STACK_INIT_SIZE 100 //存储空间初始分配量
#define STACKINCREAMENT 10 //存储分配空间的分配增量
#define MAZE_RANGE 80          //迷宫数组范围

#include <malloc.h>
#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>

using namespace std;

typedef int Status;
typedef struct {//定义坐标类型
int x; 
int y;
}PosType;

typedef struct {	
int ord;	
PosType seat;	
int di;		
}SElemType;

typedef struct {	//定义顺序存储的栈
SElemType * top;	//栈顶指针
SElemType * base;	//栈底指针
int stacksize;		//当前已分配的存储空间
}SqStack;

typedef struct {	//定义迷宫类型 
int m,n;
int maze[MAZE_RANGE][MAZE_RANGE]; //迷宫的最大范围
}MazeType;

Status InitStack(SqStack &s)
{ 

s.base = (SElemType *) malloc( STACK_INIT_SIZE * sizeof(SElemType) );
if(!s.base) 
	return (OVERFLOW); 
s.top = s.base;
s.stacksize = STACK_INIT_SIZE;
return OK;

}

Status Push(SqStack &s,SElemType &e)
{//插入元素e为新的栈顶元素

SElemType * newbase;
if(s.top - s.base >= s.stacksize){	//栈满，追加存储空间 
newbase = (SElemType *) realloc(s.base,(s.stacksize+STACKINCREAMENT)*sizeof(SElemType));
if(!newbase) 
	return(OVERFLOW);
s.base = newbase;
s.top = s.base + s.stacksize;
s.stacksize+=STACKINCREAMENT;
}
*s.top++ = e;
return OK;

}

Status Pop(SqStack &s,SElemType &e)
{//若栈不空，则删除s的栈顶元素,成功返回TRUE，并返回其值为e,否则，返回ERROR

if(s.top==s.base) return ERROR;
e=*--s.top;
return OK;

}
Status StackEmpty(SqStack &s)
{//若栈为空，则返回OK,否则返回ERROR

if(s.base==s.top) 
return OK;
else 
return ERROR;

}

Status Pass(MazeType &maze,PosType p)
{// 当坐标上的值为1时,可以通过,返回OK，否则返回ERROR
if(maze.maze[p.y][p.x]==1)  //X是列，Y是行
return OK;
else 
return ERROR;
}

void FootPrint(MazeType &maze,PosType &p)
{ //当位置可以通过时,把地图标记为2,留下痕迹

maze.maze[p.y][p.x]=2;

}

void MarkPrint(MazeType &maze,PosType &p)
{//当位置不可以通过时,把地图标记为3,留下痕迹

maze.maze[p.y][p.x]=3;

}


void NextPos(PosType &e,int di)
{//寻找下一位置

switch (di){
case 1: e.x++;break;	//右移
case 2: e.y++;break;	//下移
case 3: e.x--;break;	//左移
case 4: e.y--;break;	//上移
}//switch

}

Status MazePrint(MazeType maze)
{ //打印迷宫
	system("color F1");
	//system("cls");
cout<<"迷宫图为:(空白表示通路,■表示墙)"<<endl;

for(int i=0;i<maze.m;i++)
{
	for(int j=0;j<maze.n;j++)
		//cout<<maze.maze[i][j]<<' ';
	    if(maze.maze[i][j]==6)
		    cout << "★";
	    else  if(maze.maze[i][j]==0)
			cout << "■";
		else if(maze.maze[i][j]==1)
			cout <<" "<<" ";
		else if(maze.maze[i][j]==2)
			cout << '*'<<' ';
		else if(maze.maze[i][j]==3)
			cout << '-'<<' ';
	        cout<<endl;		//一行打印完后换行
} 
cout<<endl;
return OK;

}

Status CreatMaze(MazeType &maze,PosType &start,PosType &end)
{
//当flag等于1时，用户通过键盘输入 m,n创建m行,n列迷宫
//当flag等于0时，调用一个已创建好的15行，15列的迷宫

int flag = 0; //选择标志
system("color F0");
cout<<"1:咱自己建立一个迷宫"<<endl<<"0:我很懒，调用默认迷宫"<<endl;
cin>>flag;
if(flag == 1) 
{
cout<<"#表示墙，用空白表示通路"<<endl;
cout<<"请输入迷宫的行数:"<<endl;
cin>>maze.m;
cout<<"请输入迷宫的列数:"<<endl;
cin>>maze.n;
int y=1; //建立数组行标志位
for(int i=0;i<maze.m;i++)	//录入迷宫图
{
	printf("请输入第%d行的元素:",y);
	cout<<endl;
	for(int j=0;j<maze.n;j++)
		cin>>maze.maze[i][j];
	y++;
}
}
else if(flag == 0) 
{ 
//创建默认的迷宫图

	int Temp_Maze[39][39]={
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0,
0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0,
0, 6, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0,
0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0,
0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0,
0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0,
0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0,
0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0,
0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0,
0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0,
0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0,
0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0,
0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0,
0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0,
0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0,
0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0,
0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0,
0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0,
0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0,
0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0,
0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0,
0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0,
0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0,
0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0,
0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0,
0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 0,
0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0,
0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0,
0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0,
0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0,
0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0,
0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0,
0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0,
0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0,
0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0,
0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0,
0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,};



maze.m=39; //行
maze.n=39; //列
for(int i=0;i<39;i++)
for(int j=0;j<39;j++)
maze.maze[i][j]=Temp_Maze[i][j];
}
else 
{
cout<<"输入不合法!!"<<endl;
return OK;
}

//MazePrint(maze); 

//cout<<"请输入迷宫入口坐标<列,行>:"<<endl; 
//cin>>start.x; 
//cin>>start.y;
//cout<<"请输入迷宫出口坐标<列,行>:"<<endl; 
//cin>>end.x; 
//cin>>end.y; 
return OK;

}


Status MazePath(MazeType &maze, PosType start,PosType end,SqStack &s)
{ //寻找一条最近的迷宫图，并用栈s记录其路径 ，找到返回OK，否则，返回ERROR

PosType curpos;	//当前位置
int curstep=1;	//当前步数
SElemType e;

curpos.x = start.x;
curpos.y = start.y;
do
{
if (Pass(maze,curpos)){//当前位置可以通过，既是未曾走过的通道块
FootPrint(maze,curpos);//留下足迹
//把入口作为路径的第一步
e.di=1;
e.ord=curstep;
e.seat.x=curpos.x;
e.seat.y=curpos.y;
Push(s,e);
if (curpos.x==end.x && curpos.y==end.y)
	return OK;
NextPos(curpos,1);//以右侧探索为优先
curstep++;//探索下一步
}
else{//当前位置不可能通过 
if(!StackEmpty(s)){
Pop (s,e);
while(e.di==4&&!StackEmpty(s)){
MarkPrint(maze,e.seat);//留下不能通过的标记，并退回一步
Pop(s,e);
}
if(e.di<=4){
e.di++;
Push(s,e);//换下一个方向探索
NextPos(e.seat,e.di);//设定当前位置是该新方向上的相邻块
curpos.x=e.seat.x;
curpos.y=e.seat.y;

}
}
}
}while(!StackEmpty(s));

cout<<"###########死迷宫###########"<<endl;
return FALSE;

}


Status  PeopleMaze(MazeType maze)
{
  system("color F1");
  int  i,j;
   char c = getch();
  for(int i=0;i<maze.m;i++)
      {
        for(int j=0;j<maze.n;j++)
         if(maze.maze[i][j]==6)
          {   
			  maze.maze[i][j]=1;
			
			 while(1)
              {
              c=getch(); 
              system("cls");
			   cout<<"Play the game!" << endl;
               switch(c) 
               { 
               case 27: 
	             cout<<"Esc";break;
               case 75: 
				   j--;  if(maze.maze[i][j]==1) {maze.maze[i][j]=6; MazePrint(maze);maze.maze[i][j]=1;}
				         else if(maze.maze[i][j]==0)     { j++;maze.maze[i][j]=6; MazePrint(maze);maze.maze[i][j]=1;} 
					//	 else if(maze.maze[i][j]==6)     {j++; maze.maze[i][j]=1; MazePrint(maze);j--;}
				    break;    // else  MazePrint(maze); 
               case 72: 
                   i--;  if(maze.maze[i][j]==1) {maze.maze[i][j]=6; MazePrint(maze);maze.maze[i][j]=1;}
			       	     else if(maze.maze[i][j]==0)    {  i++;maze.maze[i][j]=6;  MazePrint(maze);maze.maze[i][j]=1;}
					//	 else if(maze.maze[i][j]==6)     {  i++;maze.maze[i][j]=1; MazePrint(maze);i--;}
				     break;   //  else  MazePrint(maze);
               case 77: 
                   j++;  if(maze.maze[i][j]==1) {maze.maze[i][j]=6; MazePrint(maze);maze.maze[i][j]=1;}
				         else if(maze.maze[i][j]==0)     {j--;maze.maze[i][j]=6;  MazePrint(maze);maze.maze[i][j]=1;}
					//	 else if(maze.maze[i][j]==6)     { j--;maze.maze[i][j]=1; MazePrint(maze);j++;}
				        break;// else MazePrint(maze); 
               case 80: 
                   i++;  if(maze.maze[i][j]==1)   {maze.maze[i][j]=6; MazePrint(maze);maze.maze[i][j]=1;}
				         else if(maze.maze[i][j]==0)    {i--; maze.maze[i][j]=6; MazePrint(maze); maze.maze[i][j]=1;  }
					//	 else if(maze.maze[i][j]==6)     { i--;maze.maze[i][j]=1; MazePrint(maze);i++;}
				         break; //else MazePrint(maze);
               }
		   if(c==27)
                break;
		   else if(i==37&&j==37)
		   {cout<<"Congratulation!"<<endl;return TRUE;}
			  }
		
		    
          }     
   }
	return TRUE;
}

void main()
{

MazeType maze;
PosType end;
PosType start;
start.x=3;
start.y=1;
end.x=38;
end.y=38;
SqStack s;

InitStack(s); 
CreatMaze(maze,start,end); 
//MazePath(maze,start,end,s); 
//cout<<"用图(*表示走过的路,-表示走过但又退回来的路)表示为:"<<endl;
MazePrint(maze); 
PeopleMaze(maze);
//MazePrint(maze); 
system("pause");

}