창고 의 응용 - 미궁 문제 - 데이터 구조

창고 의 기본 적 인 응용 중 하나 로 미로 문 제 를 해결 하 는데 주로 창고 의 귀속 작용 을 이용한다.
바로 검색 을 거 슬러 올 라 가 두 번 썼 고, 첫 번 째 작은 문 제 는 두 시 까지 조정 되 지 않 았 으 며, 다음날 아예 다시 썼 고, 한 번 에 나 왔 다.
뒤의 몇 가지 예 가 운행 되 었 는데 문제 가 없 었 습 니 다. 어떤 문 제 는 잠시 발견 되 지 않 았 을 수도 있 습 니 다. 주로 OJ 와 같 지 않 습 니 다. 사람들 은 이미 데 이 터 를 구 조 했 기 때문에 자신 은 게 으 르 게 데 이 터 를 구 조 했 습 니 다.
예 코드:

#include
#include
#include

#define Initstacksize 100
#define Increase 100


typedef struct PosType     //   
{
	int x;
	int y;
}PosType; 

typedef struct MazeType
{
	char **maze;    //    
	int **mark;    //    
	int row;    //       
	int col;   //     
}MazeType;

typedef struct SElemType
{
	int ord;   //     
	PosType seat;   //     
	int dir; //   
}SElemType;

typedef struct SqStack   //  
{
	SElemType *base;
	SElemType *top;
	int stacksize;
}SqStack;

void CreatMaze(MazeType &ma)  //     
{
	int i,j;
	char ch;
	printf("Input the row and the col of the maze:
");
	scanf("%d%d",&ma.row,&ma.col);
	ma.maze=(char**)malloc(Initstacksize*sizeof(char*));
	ma.mark=(int**)malloc(Initstacksize*sizeof(int*));
	ch=getchar();
	for(i=0;i=maa.row || std.y>=maa.col || maa.maze[std.x][std.y]=='#' || maa.mark[std.x][std.y]>0)
			return 0;
	else return 1;
}

SElemType UpdatE(PosType p,int step,int di)  //      ：  ，  ，     
{
	SElemType ee;
	ee.ord=step;
	ee.dir=di;
	ee.seat=p;
	return ee;
}

void PushStack(SqStack &S,SElemType ee)  //   
{
	if(S.top-S.top>=S.stacksize)
	{
		S.base=(SElemType*)realloc(S.base,(Increase+Initstacksize)*sizeof(SElemType));
		S.top=S.base+S.stacksize;
		S.stacksize+=Increase;
	}
	*S.top++=ee;
}

bool EmptyStack(SqStack S)   //        
{
	if(S.base==S.top) return true;
	else return false;
}

void MakePrint(MazeType &maa,PosType p)  //        
{
	maa.mark[p.x][p.y]=1;
}

PosType NextPos(PosType p,int di)  //      
{
	PosType np;
	np=p;
	switch(di)
	{
		case 1:np.x++;break; //  
		case 2:np.y++;break; //  
		case 3:np.x--;break; //  
		case 4:np.y--;break; //  
		default:break; 
	}
	return np;
}

void PopStack(SqStack &ss,SElemType &ee)  //              
{
	ss.top--;
	ee=*ss.top;
}

void NoPrint(MazeType &maa,PosType p)  //             
{
	maa.mark[p.x][p.y]=2;
}

int MazePath(MazeType ma,SqStack &s,PosType st,PosType ed)   //     
{
	PosType curpos;
	SElemType e;
	int curstep;
	curstep=1;
	curpos=st;
	if(!PassOk(st,ma)) return 0;//    OK 
	MakePrint(ma,curpos);    //      
	e=UpdatE(curpos,curstep,1); //       
	PushStack(s,e);  //    ，      
	curpos=NextPos(curpos,1); //     
	curstep++;
	while(!EmptyStack(s)) 
	{
		if(PassOk(curpos,ma))
		{
			MakePrint(ma,curpos);
			e=UpdatE(curpos,curstep,1);
			PushStack(s,e);
			if(curpos.x==ed.x&& curpos.y==ed.y) return 1; //     
			curpos=NextPos(curpos,1);
			curstep++;
		}
		else
		{
			if(!EmptyStack(s))
			{
				PopStack(s,e);  //  
				while(e.dir==4 && !EmptyStack(s))  //       ，      
				{
					NoPrint(ma,e.seat);   //         
					PopStack(s,e);
				}
				if(e.dir<4)  //       
				{
					e.dir++;
					PushStack(s,e);  //           ，             ，          
					curpos=NextPos(e.seat,e.dir); //      
				} 
			}//if
		}//else
	}//while 
	return 0;
}

void DisplayMarkPath(MazeType maa)  //    ， 
{
	int i,j;
	for(i=0;i