xc_maze.cpp

迷宫 数据结构的一个作业 包含.cpp源文件

// xc_maze.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
using namespace std;


#define RANGE 22
#define STACK_INIT_SIZE 20
#define STACKINCREMENT 10


struct Postype
{	int x,y;
};
struct Pathnode
{	int ord;
	Postype seat;
	int di;
};
struct Stack
{	Pathnode* top;
    Pathnode* base;
	int stacksize;
};
struct Mazetype
{	int m,n;
	char arr[RANGE][RANGE];
}maze;



bool init_stack(Stack& s);
bool destroy_stack(Stack& s);
bool push(Stack& s,Pathnode e);
bool pop(Stack& s,Pathnode &e);
bool stack_empty(Stack s);

bool foot_print(Postype pos);
bool pass(Postype pos);
bool mark_print(Postype pos);
Postype next_pos(Postype pos, int direct);

bool maze_path(Mazetype maze,Postype start,Postype end);
bool init_maze(Mazetype maz);
bool output_maze(Mazetype ma);
bool input_maze();







int main()
{	int ButtonGet;
	int right=1;
	Postype StartPos,EndPos;

	init_maze(maze);
	cout<<"the initial maze:"<<endl;
	output_maze(maze);

	cout<<"please make the maze:"<<endl;
	input_maze();
	cout<<"now the maze is like this:"<<endl;
	output_maze(maze);

	cout<<"please give the start-position(x/y):"<<endl;
	cin>>StartPos.x>>StartPos.y;
	cout<<"please give the end-position(x/y):"<<endl;
	cin>>EndPos.x>>EndPos.y;
	
	do{	cout<<"press any button, then i will give you the path:"<<endl;
		ButtonGet=getchar();
	}while(right=0);
	maze_path(maze,StartPos,EndPos);
	
	cout<<"the maze-path is like this:"<<endl;
	output_maze(maze);

	return 0;
}



bool maze_path(Mazetype maze,Postype start,Postype end)
{	Postype curpos;
	int curstep;
	Pathnode e;
	Stack s;

	init_stack(s);
	curpos=start;
	curstep=1;
	do{	if(pass(curpos))
		{	foot_print(curpos);
			e.ord=curstep;
			e.seat=curpos;
			e.di=1; 
			push(s,e);
			if(curpos.x==end.x&&curpos.y==end.y) 
			{	destroy_stack(s);
				return true;
			}
			curpos=next_pos(curpos,e.di);
			curstep++;
		}
		else
		{	if(!stack_empty(s))
			{	pop(s,e);
				while(e.di==4&&!stack_empty(s))
				{	mark_print(e.seat);
					pop(s,e);
				}
				if(e.di<4)
				{	e.di++;
					push(s,e);
					curpos=next_pos(e.seat,e.di);
				}
			}
		}
	}while(!stack_empty(s));
	return false;
}

bool init_maze(Mazetype ma)
{	do{ cout<<"please input the line number(<=20):"<<endl;
		cin>>ma.m;
		/*cout<<ma.m<<endl;*/
	}while(ma.m>RANGE-2);
	do{	cout<<"please input the column number(<=20):"<<endl;
		cin>>ma.n;
	}while(ma.n>RANGE-2);
	
	for(int i=0;i<=ma.n + 1;i++)
		for(int j=0;j<=ma.m + 1;j++)
		{	ma.arr[i][j]='0';
		    /*cout<<ma.arr[i][j]<<endl;*/
		}
	for(i=0;i<=ma.n + 1;i++)
	{	ma.arr[0][i]='w';
		ma.arr[ma.m + 1][i]='w';
		/*cout<<ma.arr[0][i]<<endl;*/
	}
	for(int j=0;j<=ma.m + 1;j++)
	{	ma.arr[j][0]='w';
		ma.arr[j][ma.n + 1]='w';
		/*cout<<ma.arr[j][0]<<endl;*/
	}

	/*cout<<"done"<<endl;
	output_maze(maze);
	cout<<"done2"<<endl;*/
	return true;
}

bool output_maze(Mazetype ma)
{	for(int i=0;i<=ma.m + 1;i++)
	{	for(int j=0;j<=ma.n + 1;j++)
		{	cout<<ma.arr[i][j];
			cout<<"done";
		}	
	cout<<endl;
	}
	cout<<ma.m<<ma.n<<endl;
	return true;
}
bool input_maze()
{	int sigx,sigy;
	char sigcotin;
	do{	
		cout<<"please input the line-position:"<<endl;
		cin>>sigx;
		cout<<"please input the column-position:"<<endl;
		cin>>sigy;
		maze.arr[sigx][sigy]='w';
		
		cout<<"continue?"<<endl;
		cin>>sigcotin;
	}while(sigcotin=='Y');
	return true;
}




bool init_stack(Stack& s)
{	s.base=(Pathnode*)malloc(STACK_INIT_SIZE*sizeof(Pathnode));
	if(!s.base) return false;
	s.top=s.base;
	s.stacksize=STACK_INIT_SIZE;
	return true;
}

bool destroy_stack(Stack& s)
{	if(!s.base) return false;
	else if(s.top==s.base) free(s.base);
		 else 
		 {	s.top=s.base;
			free(s.base);
		 }
	return true;
}

bool push(Stack& s,Pathnode e)
{	if(s.top-s.base>=s.stacksize)
	{	s.base=(Pathnode*)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(Pathnode));
		if(!s.base) return false;
		s.top=s.base+s.stacksize;
		s.stacksize+=STACKINCREMENT;
	}
	*s.top++=e;
	return true;
}

bool pop(Stack& s,Pathnode& e)
{	if(s.top==s.base) 
		return false;
	e= *(--s.top);
	return true;
}

bool stack_empty(Stack s)
{	if(s.base==s.top) 
		return true;
	else 
		return false;
}






bool pass(Postype pos)
{	if(!(maze.arr[pos.x][pos.y]=='*'||'?'||'W'))
		return true;
	else
		return false;
}

Postype next_pos(Postype pos,int direct)
{	switch(direct)
	{	case 1:pos.y=pos.y+1;break;
		case 2:pos.x=pos.x+1;break;
		case 3:pos.y=pos.y-1;break;
		case 4:pos.x=pos.x-1;
	}
	return pos;
}

bool foot_print(Postype pos)
{	if(pos.x>maze.m || pos.y>maze.n) 
		return false;
	maze.arr[pos.x][pos.y]='?';
	return true;
}

bool mark_print(Postype pos)
{	if(pos.x>maze.m || pos.y>maze.n) 
		return false;
    maze.arr[pos.x][pos.y]='*';
	return true;
}