path.h

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

#ifndef PATH_H_
#define PATH_H_

#include "stdio.h"
#include "stdlib.h"
#include "iostream.h"

const int MAX_STACK_SIZE=100;
const int SIZEX_MAZE=22;
const int SIZEY_MAZE=22;
int maze[SIZEX_MAZE][SIZEY_MAZE];
bool mark[SIZEX_MAZE][SIZEY_MAZE];
bool mark2[SIZEX_MAZE][SIZEY_MAZE];
const int EXIT_ROW=SIZEX_MAZE-2;
const int EXIT_COL=SIZEY_MAZE-2;
class element;
class Stack;
class offsets;
void GenerateMaze();
void SearchPath();
void InitMark();
void ShowMaze();

class element
{
public:	
	int row;
	int col;
	int dir;
};

class Stack
{
private:
	int top;
	element error;
public:
	element	stack[MAX_STACK_SIZE];
public:	
	Stack():top(-1)
	{}
	void StackEmpty()
	{
		top=-1;
	}
	element DeleteStack()
	{
		if(top==-1)
			return error;
		else
			return stack[top--];
	}
	bool AddStack(const element & pa)
	{
		if(top==MAX_STACK_SIZE-1)
			return false;
		else
		{
			stack[++top]=pa;
			return true;
		}
	}
	bool AddStack(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;
	}
	int GetLength()
	{
		return top;
	}
	~Stack()
	{}

};
class offsets
{
	public:
		int vert;
		int horiz;
	public:
		void GetValue(int vert=0,int horiz=0)
		{
			this->vert=vert;
			this->horiz=horiz;
		}
};
offsets	move[8];

void GenerateMaze()
{
	int i,j;
	int k;
	for(i=0;i<SIZEX_MAZE;i++)
		for(j=0;j<SIZEY_MAZE;j++)
			maze[i][j]=1;
	i=1;j=1;
	maze[i][j]=0;

	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()%3;
		if(k==0)
		{
			i++;
			maze[i][j]=0;
			continue;
		}
		if(k==1)
		{
			i++;j++;
			maze[i][j]=0;
			continue;
		}
		if(k==2)
		{
			j++;
			maze[i][j]=0;
			continue;
		}
	}
	// rand();
	k=0;
	while(k<SIZEX_MAZE*4/5)
	{
		i=rand()%(SIZEX_MAZE-10)+4;
		j=rand()%(SIZEY_MAZE-10)+4;
		maze[i][j]=0;
		k++;
	}

	// secrete  part one
	int e1,f1;
	i=rand()%6+2;
	j=SIZEY_MAZE-2-rand()%7;
	e1=SIZEX_MAZE-2-rand()%6;
	f1=rand()%6+2;
	while(i!=e1||j!=f1)
	{
		if(i==e1)
		{
			while(j!=f1)
				maze[i][--j]=0;
			break;
		}
		if(j==f1)
		{
			while(i!=e1)
				maze[++i][j]=0;
			break;
		}
		int p=rand()%3;
		if(p==0)
		{
			i++;
			maze[i][j]=0;
			continue;
		}
		if(p==1)
		{
			i++;j--;
			maze[i][j]=0;
			continue;
		}
		if(p==2)
		{
			j--;
			maze[i][j]=0;
			continue;
		}
	}
	
	//secret part two 
	i=rand()%6+4;
	j=SIZEY_MAZE-7-rand()%7;
	e1=SIZEX_MAZE-7-rand()%6;
	f1=rand()%6+6;
	while(i!=e1||j!=f1)
	{
		if(i==e1)
		{
			while(j!=f1)
				maze[i][--j]=0;
			break;
		}
		if(j==f1)
		{
			while(i!=e1)
				maze[++i][j]=0;
			break;
		}
		int p=rand()%3;
		if(p==0)
		{
			i++;
			maze[i][j]=0;
			continue;
		}
		if(p==1)
		{
			i++;j--;
			maze[i][j]=0;
			continue;
		}
		if(p==2)
		{
			j--;
			maze[i][j]=0;
			continue;
		}
	}
	


}
void ShowMaze()
{
	int i=0,j=0;
	for(i=1;i<SIZEX_MAZE-1;i++)
	{
		for(j=1;j<SIZEY_MAZE-1;j++)
			cout<<maze[i][j]<<" ";
		cout<<endl;
	}

}
void InitMark()
{

	int i,j;
	// setvalue of the move;
	move[0].GetValue(-1,0);
	move[1].GetValue(-1,1);
	move[2].GetValue(0,1);
	move[3].GetValue(1,1);
	move[4].GetValue(1,0);
	move[5].GetValue(1,-1);
	move[6].GetValue(0,-1);
	move[7].GetValue(-1,-1);
	// initialize the mark
	for(i=0;i<SIZEX_MAZE;i++)
		for(j=0;j<SIZEY_MAZE;j++)
			mark[i][j]=0;
	for(i=0;i<SIZEX_MAZE;i++)
		for(j=0;j<SIZEY_MAZE;j++)
			mark2[i][j]=0;
}

long SearchPath(Stack & _stack)
{
	int row,col,next_row,next_col,dir;
	long count=0;
	bool found=false;
	element position;
	InitMark();
	mark[1][1]=true;
	_stack.AddStack(1,1,1);
	while(!_stack.Empty()&&!found)
	{
		position=_stack.DeleteStack();
		row=position.row;
		col=position.col;
		dir=position.dir;
		while(dir<8&&!found)
		{
			
			next_row=row+move[dir].vert;
			next_col=col+move[dir].horiz;
			if(next_row==EXIT_ROW&&next_col==EXIT_COL)
				found=true;
			else	
				if(!maze[next_row][next_col]&&!mark[next_row][next_col])
				{
					mark[next_row][next_col]=1;
					position.row=row;
					position.col=col;
					position.dir=++dir;
					_stack.AddStack(position);
					row=next_row;
					col=next_col;
					dir=0;			
					count++;

				}
				else
					++dir;
		}
	}
	if(found)
	{
		return count;
	}
	else
		return 0;
}
long SearchPath(Stack &_stack,Stack &_stack2)
{
	int row,col,next_row,next_col,dir;
	int row2,col2,next_row2,next_col2,dir2;
	long count=0;
	long count2=0;
	bool found=false;
	element position;
	element position2;
	InitMark();
	mark[1][1]=true;
	mark2[1][1]=true;
	_stack.AddStack(1,1,1);
	_stack2.AddStack(1,1,7);

	while(!(_stack.Empty()&&_stack2.Empty())&&!found)
	{
		count++;
		position=_stack.DeleteStack();
		row=position.row;
		col=position.col;
		dir=position.dir;
		while(dir<8&&!found)
		{
			
			next_row=row+move[dir].vert;
			next_col=col+move[dir].horiz;
			if(next_row==EXIT_ROW&&next_col==EXIT_COL)
				found=true;
			else	
				if(!maze[next_row][next_col]&&!mark[next_row][next_col])
				{
					mark[next_row][next_col]=1;
					position.row=row;
					position.col=col;
					position.dir=++dir;
					_stack.AddStack(position);
					row=next_row;
					col=next_col;
					dir=0;
					count++;
				}
				else
					++dir;
		}

		count2++;
		position2=_stack2.DeleteStack();
		row2=position2.row;
		col2=position2.col;
		dir2=position2.dir;
		while(dir2>=0&&!found)
		{
			
			next_row2=row2+move[dir2].vert;
			next_col2=col2+move[dir2].horiz;
			if(next_row2==EXIT_ROW&&next_col2==EXIT_COL)
				found=true;
			else	
				if(!maze[next_row2][next_col2]&&!mark2[next_row2][next_col2])
				{
					mark2[next_row2][next_col2]=1;
					position2.row=row2;
					position2.col=col2;
					position2.dir=--dir2;
					_stack2.AddStack(position2);
					row2=next_row2;
					col2=next_col2;
					dir2=7;
					count2++;
				}
				else
					--dir2;
		}

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

}

void InitAll()
{
	GenerateMaze();
	InitMark();
}
#endif