데이터 구조 --- 미로 문제 풀이 (C 언어)

데이터 구조 - 미로 문제 풀이 (C 언어)

#include
#include
#define FALSE 0
#define TRUE  1
#define OK    1 
#define M     20
#define N     20
typedef struct mark //         
{
    int x;
    int y;
}Mark;
struct Element //    
{
    int x,y; //x ,y 
    int d; //      
};
typedef struct LStack //  
{
    Element elem;
    struct LStack *next;
}*PLStack;
/*************   ****************/
int InitStack(PLStack &S)//    
{
    S=NULL;
    return OK;
}
int StackEmpty(PLStack S)//       
{
    if(S==NULL)
        return OK;
    else
        return FALSE;
}
int Push(PLStack &S, Element e)//    
{
    PLStack p;
    p=(PLStack)malloc(sizeof(LStack));
    p->elem=e;
    p->next=S;
    S=p;
    return OK;
}
int Pop(PLStack &S,Element &e) //     
{
    PLStack p;
    if(!StackEmpty(S))
    {
        e=S->elem;
        p=S;
        S=S->next;
        free(p);
        return OK;
    }
    else
        return FALSE;
}


/*************    *******************/
void initmaze(int maze[M][N])
{
    int m,n; //   ,  
    printf("         m=");
    scanf("%d",&m);
    printf("         n=");
    scanf("%d",&n);
    printf("
          :
     ,0   ,1   
",m,n);

    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            scanf("%d",&maze[i][j]);
    printf("      (     )
");     //     
    for(int i=0;i<=m+1;i++) //     
    {
        maze[i][0]=1;
        maze[i][n+1]=1;
    }
    for(int j=0;j<=n+1;j++)
    {
        maze[0][j]=1;
        maze[m+1][j]=1;
    }
    
     for(int i=0;i<=m+1;i++) //    
    {
        for(int j=0;j<=n+1;j++)
            printf("%d ",maze[i][j]);
        printf("
");
    }

}



/*************       *************/
void MazePath(struct mark start,struct mark end,int maze[M][N],int diradd[4][2])
{
    int i,j,d;
	int a,b;
    Element elem,e;
    PLStack S1,S2;
    InitStack(S1);
    InitStack(S2);
    maze[start.x][start.y]=2; //       
    elem.x=start.x;
    elem.y=start.y;
    elem.d=0; //   0   ,  1；  2； 3 ；  4 
    Push(S1,elem);
    while(!StackEmpty(S1)) //          
    {
        Pop(S1,elem);
        i=elem.x;
        j=elem.y;
        d=elem.d+1; //     
        while(d<=4) //         
        {
            a=i+diradd[d-1][0];
            b=j+diradd[d-1][1];
            if(a==end.x && b==end.y && maze[a][b]==0) //     
            {
                elem.x=i;
                elem.y=j;
                elem.d=d;
                Push(S1,elem);
                elem.x=a;
                elem.y=b;
                elem.d=6; //     -1         
                Push(S1,elem);
                printf("
1=  2=  3=  4=  6      

   :(   ,   ,  )
");
                while(S1) //       
                {
                    Pop(S1,e);
                    Push(S2,e);
                }
                while(S2) //     
                {
                    Pop(S2,e);
                    printf("->(%d,%d,%d)",e.x,e.y,e.d);
                }
                return; //      ，   break,     ，exit      ，  return     
            }
            if(maze[a][b]==0) //            
            {
                maze[a][b]=2; //      
                elem.x=i;
                elem.y=j;
                elem.d=d;
                Push(S1,elem); //      
                i=a;           //         
                j=b;
                d=0;
            }
            d++;
        }
    }
    printf("              
");
}

int main(){
    int mg[M][N];
    Mark start,end; //start,end        
    int add[4][2]={{0,1},{1,0},{0,-1},{-1,0}};//                  
    initmaze(mg);//    
    printf("        ,   [    ]
");
    scanf("%d,%d",&start.x,&start.y);
    printf("        ,   [    ]
");
    scanf("%d,%d",&end.x,&end.y);
    MazePath(start,end,mg,add); //find path
	
	return 0;
}