창고 와 대열 로 미궁 문 제 를 풀다

1: ① 순서 스 택 을 정의 합 니 다.
    ② 、 미로 에서 벗 어 나 는 코드 작성 하기;
    ③ 주 함 수 를 작성 한다.
1. 창고:

#include
#include
#include
#include
#define MaxSize 100
//①、       ；
typedef struct
{  int i;		 
   int j;		 
   int di;		 
 } Box;		 
typedef struct
{  Box data[MaxSize];
   int top;		 
 } StType;
//②、        ；
bool mgpath(int xi,int yi,int xe,int ye)	
{  int i,j,k,di,find;
   StType st;			
   st.top=-1;			
   st.top++;			
   st.data[st.top].i=xi; st.data[st.top].j=yi;
   st.data[st.top].di=-1; mg[xi][yi]=-1; 
   while (st.top>-1)		
   {	i=st.data[st.top].i;j=st.data[st.top].j;
	di=st.data[st.top].di;	
	if (i==xe && j==ye)	
	{   printf("      :
");
	    for (k=0;k<=st.top;k++)
	    {  printf("\t(%d,%d)",st.data[k].i,st.data[k].j);
		 if ((k+1)%5==0)	
			printf("
");
	    }
	    printf("
");
	    return true;		
	}
   find=0;
   while (di<4 && find==0)	
   {  di++;
      switch(di)
      {
      case 0:i=st.data[st.top].i-1;j=st.data[st.top].j;
             break;
	  case 1:i=st.data[st.top].i;j=st.data[st.top].j+1;
             break;
	  case 2:i=st.data[st.top].i+1;j=st.data[st.top].j;
             break;
	  case 3:i=st.data[st.top].i,j=st.data[st.top].j-1;
             break;
	   }
	  if (mg[i][j]==0) find=1; 
    }
  if (find==1)			 
  {  st.data[st.top].di=di;	 
     st.top++;			 
     st.data[st.top].i=i; st.data[st.top].j=j;
     st.data[st.top].di=-1;
     mg[i][j]=-1;	
  }
  else		
  {	mg[st.data[st.top].i][st.data[st.top].j]=0;
	st.top--;	
   }
 }
 return false;	
}
//③、     ：

  
        :
	(1,1) (1,2)	(2,2) (3,2) (3,1) 
	(4,1) (5,1) (5,2) (5,3) (6,3) 
	(6,4) (6,5) (5,5) (4,5) (4,6) 
	(4,7) (3,7) (3,8) (4,8) (5,8) 
	(6,8) (7,8) (8,8)

2. 대열

#include
#include
#include
#include
#define MaxSize 100
//①、       ；
typedef struct 
{  int i,j;		      
   int pre;		      
} Box;			
typedef struct
{  Box data[MaxSize];
   int front,rear;
} QuType;
//②、        ；：
bool mgpath1(int xi,int yi,int xe,int ye)	
{  int i,j,find=0,di;
   QuType qu;		
   qu.front=qu.rear=-1;
   qu.rear++;
   qu.data[qu.rear].i=xi; qu.data[qu.rear].j=yi;
   qu.data[qu.rear].pre=-1;	
   mg[xi][yi]=-1;		  
   while (qu.front!=qu.rear && !find)  
   {  qu.front++;             
	i=qu.data[qu.front].i; j=qu.data[qu.front].j;
	if (i==xe && j==ye)     
	{  find=1; print(qu,qu.front); return true; }
	for (di=0;di<4;di++)    
	{  switch(di)
	   {
	   case 0:i=qu.data[qu.front].i-1; 
                j=qu.data[qu.front].j;    break;
	   case 1:i=qu.data[qu.front].i; 
                j=qu.data[qu.front].j+1;  break;
	   case 2:i=qu.data[qu.front].i+1;
                j=qu.data[qu.front].j;    break;
	   case 3:i=qu.data[qu.front].i;
                j=qu.data[qu.front].j-1;  break;
	   }
	   if (mg[i][j]==0)
	   {  qu.rear++;		
		  qu.data[qu.rear].i=i; qu.data[qu.rear].j=j;
		  qu.data[qu.rear].pre=qu.front; 
		  mg[i][j]=-1;
  	   }
	}
   }
   return false;	
}
//③、     ：

        :
　 (1,1)(2,1)(3,1)(4,1)(5,1)
    (5,2)(5,3)(6,3)(6,4)(6,5)
    (7,5)(8,5)(8,6)(8,7)(8,8)

      스 택 과 대기 열 두 가지 방법 으로 미로 문 제 를 쓴다.스 택 과 대열 의 공통점 과 차이 점 을 알 게 되 었 습 니 다.창 고 는 역 추적 을 통 해 진행 되 었 다.거 슬러 올 라 가기 편리 하도록 갈 수 있 는 사각형 에 대해 모두 창고 에 들 어가 다음 에 갈 수 있 는 위 치 를 탐색 하고 이 갈 수 있 는 위 치 를 창고 에 보관 해 야 한다.이것 은 창고 가 미로 문제 에 대해 선택 한 방법 이다.대기 열 은 출구 를 찾 을 때 까지 대기 열의 특징 을 이용 하여 한 층 한 층 밖으로 확장 할 수 있 는 점 입 니 다.우리 뒤에서 그림 에서 배 운 범위 우선 검색 방법 과 같다.실험 기간 동안 알파벳 대소 문자 가 많 았 다.그래서 헷 갈 려 서 문제 가 생 겼 어 요.쉼표 와 분 호 를 잘못 알 기도 한다.