microbeway.h

maze目录下包含了4个迷宫相关的源代码：简单的迷宫生成算法、复杂的迷宫生成算法、简单的迷宫搜索算法、复杂的迷宫搜索算法

// Copyright: 胡小民，丁展 2002.5

#include "stdio.h"
#include "stdlib.h"
#include "iostream.h"
#include "maze.h"
#include "mazeMake.h"
/*
const int MAX_MStack_SIZE=1000;


const int SIZEX_MAZE=15;
const int SIZEY_MAZE=15;

const int EXIT_ROW=SIZEX_MAZE-2;
const int EXIT_COL=SIZEY_MAZE-2;

const int MAX_ANT_NUM=4;


int maze[SIZEX_MAZE][SIZEY_MAZE];		
bool mark[SIZEX_MAZE][SIZEY_MAZE];		// record that some path is not accessable
int pos[SIZEX_MAZE][SIZEY_MAZE];		// record all objects position at the same time

// tell others that this path cannot be accessed in fact it describe the new maze

bool found=false;
int step=0;
*/
//class element;
class MStack;
//class offsets;

//int Max(int x,int y ,int z,int w);
//void GenerateMaze();
long  MSearchPath(MStack& _MStack);
void MInitMark();
//void ShowMaze();
//void SimpleMaze();
void MAllocate(MStack _MStackarray[],int n);
void MInitAll();
int MMin(int x,int y ,int z,int w);
/*
bool Square1(int i,int j)
{
	if(maze[i-1][j]&&maze[i][j-1]&&maze[i-1][j-1])
		return true;
	return false;
}
bool Square0(int i,int j)
{
	if(!maze[i-1][j]&&!maze[i][j-1]&&!maze[i-1][j-1])
		return true;
	return false;
}
//----------------------------//
class element
{
public:
	int row;
	int col;
	int dir;
};*/
/*
bool EqualElement(const element a,const element b)
{
	if(a.col==b.col&&a.row==b.row)
		return true;
	else
		return false;
}*/
/*
class offsets
{
	public:
		int vert;
		int horiz;
	public:
		void GetValue(int vert=0,int horiz=0)
		{
			this->vert=vert;
			this->horiz=horiz;
		}
};*/
//---------------------------//
//offsets	move[4];

class MStack
{
private:
	int top;
	element error;
	int count;
public:
	element stack[MAX_STACK_SIZE];
public:
	bool classmark[CONST_MAZEX][CONST_MAZEY];
	int method; // method是对走法的处理，顺时针，逆时针等等
public:
	MStack():top(-1)
	{
		MMinitMark();
	}
	void NewAntsCame()
	{
		MMinitMark();
		classmark[1][1]=true;
		AddMStack(1,1,1);
		row=1;
		col=1;	
		dir=1;
		next_row=0;
		next_col=0;
		dir=0;
		count=0;
		pos[1][1]++;
		//------------------
		count++;
		position=DeleteMStack();
		row=position.row;
		col=position.col;
		dir=position.dir;

	}
	void SetDir(int dir)
	{
		this->dir=dir;
	}
	void MStackEmpty()
	{
		top=-1;

	}
	element DeleteMStack()
	{
		if(top==-1)
			return error;
		else
			return stack[top--];
	}
	bool AddMStack(const element & pa)
	{
		if(top==MAX_STACK_SIZE-1)
			return false;
		else
		{
			stack[++top]=pa;
			return true;
		}
	}

	bool AddMStack(int row,int col,int dir)
	{
		if(top==MAX_STACK_SIZE-1)
			return false;
		else
		{
			top++;
			stack[top].row=row;
			stack[top].col=col;
			stack[top].dir=dir;
			return true;
		}
	}
	bool Empty()
	{
		if(top==-1)
			return true;
		else
			return false;
	}
	void MMinitMark();
//	
private:
	int row,col,next_row,next_col,dir;
	element position;
public:
	int MSearchPathStepByStep();
	bool TestDir(int dir);
	bool TestDirection(int dir);
	int GetLength()
	{
		return top;
	}
	element GetCurrentPosition()
	{
		element temp;
		temp.row=row;
		temp.col=col;
		temp.dir=0  ;	// temp.dir=dir;
		return temp;
	}
	element GetLastPosition()
	{
		element temp;
		temp.row=next_row;
		temp.col=next_col;
		temp.dir=0;
		return temp;
	}
	~MStack()
	{}

};
//--------------independent-------------------//
void MStack::MMinitMark()
{

	int i,j;
	for(i=0;i<SIZEX_MAZE;i++)
		for(j=0;j<SIZEY_MAZE;j++)
		{
			if(maze[i][j]==1)
				classmark[i][j]=true;
			else
				classmark[i][j]=false;
		}
}

bool MStack::TestDir(int dir)	
{
	this->dir=dir;
	if(this->dir<0||this->dir>3)
		return false;
	next_row=row+move[dir].vert;
	next_col=col+move[dir].horiz;
	if(next_row==EXIT_ROW&&next_col==EXIT_COL)
	{
					found=true;					
					::pos[next_row][next_col]++;
					::pos[row][col]--;

					position.row=row;
					position.col=col;
					position.dir=--dir;
					AddMStack(position);
					row=next_row;
					col=next_col;
					dir=3;
					AddMStack(row,col,dir);
					count++;
					return true;
	}
	else
		//   墙							在栈里						
		if(!maze[next_row][next_col]&&!classmark[next_row][next_col])
		{
			classmark[next_row][next_col]=true;
			::pos[row][col]--;
			::pos[next_row][next_col]++;
			position.row=row;
			position.col=col;
			position.dir=++this->dir;
			AddMStack(position);
			row=next_row;
			col=next_col;
			this->dir=0;
			count++;
			return true;
		}

	return false;
}

bool MStack::TestDirection(int dir)
{
	this->dir=dir;
	if(this->dir<0||this->dir>3)
		return false;
	int num=0;
	while(num<4)
	{
			this->dir=this->dir%4;
			next_row=row+move[this->dir].vert;
			next_col=col+move[this->dir].horiz;
			if(next_row==EXIT_ROW&&next_col==EXIT_COL)
			{
					found=true;
					classmark[next_row][next_col]=true;					
					::pos[next_row][next_col]++;
					::pos[row][col]--;

					position.row=row;
					position.col=col;
					position.dir=--dir;
					AddMStack(position);
					row=next_row;
					col=next_col;
					dir=3;
					AddMStack(row,col,dir);
					count++;
					return true;
			}
			else
				if(!maze[next_row][next_col]&&!classmark[next_row][next_col])
				{
					classmark[next_row][next_col]=true;
					::pos[row][col]--;
					::pos[next_row][next_col]++;					
					position.row=row;
					position.col=col;
					position.dir=++this->dir;
					AddMStack(position);
					row=next_row;
					col=next_col;
					this->dir=0;
					count++;
					return true;
				}
				else
				{
					++this->dir;
					num++;
					if(num==4)
					{
							count++;
							::pos[row][col]--;
							position=DeleteMStack();
							row=position.row;
							col=position.col;
							this->dir=position.dir;
							::pos[row][col]++;
							return false;
					}
				}
		}

	return false;
}

int MStack::MSearchPathStepByStep()
{
	
	while(dir<4&&!found)
	{
			next_row=row+move[dir].vert;
			next_col=col+move[dir].horiz;
			if(next_row==EXIT_ROW&&next_col==EXIT_COL)
			{
					found=true;
					classmark[next_row][next_col]=true;
					::pos[next_row][next_col]++;
					::pos[row][col]--;

					position.row=row;
					position.col=col;
					position.dir=--dir;
					AddMStack(position);
					row=next_row;
					col=next_col;
					dir=0;
					AddMStack(row,col,dir);
					count++;
			
			}
			else
			{
				if(!maze[next_row][next_col]&&!classmark[next_row][next_col]&&!mark[next_row][next_col])
				{
					classmark[next_row][next_col]=true;
					::pos[row][col]--;
					::pos[next_row][next_col]++;
					
					position.row=row;
					position.col=col;
					position.dir=++dir;
					AddMStack(position);
					row=next_row;
					col=next_col;
					dir=0;
					count++;
					return 0;
				}
				else
				{
					++dir;
					if(dir==4)
					{
						if(!Empty()&&!found)
						{
							count++;
							::pos[row][col]--;
							position=DeleteMStack();
							row=position.row;
							col=position.col;
							dir=position.dir;
							::pos[row][col]++;
							return 0;
						}
						else
							return -1;
					}
				}
			}
	}

	if(found)
	{
		return count;
	}
	else
	{
		return 0;
	}

}
/*
void SimpleMaze()
{
	int i=1,j=1;
	maze[i][j]=0;
	int k;
	while(i!=EXIT_ROW||j!=EXIT_COL)
	{
		if(i==EXIT_ROW)
		{
			while(j!=EXIT_COL)
				maze[i][++j]=0;
			break;
		}
		if(j==EXIT_COL)
		{
			while(i!=EXIT_ROW)
				maze[++i][j]=0;
			break;
		}
		k=rand()%2;
		if(k==0)