456.c

迷宫问题

#define  TRUE 1
#define  FALSE   0
#define  OK  1
#define  ERROR   0
#define INFEASIBLE   -1
#define OVERFLOW   -2
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>
typedef  int  Status;
#define  RANGE   20
#define M 8 /* maze数组的行数 */
#define N 11 /* maze数组的列数 */


typedef struct
{
    int r,c;
}PosType;

typedef struct
{
    int m,n;
    char arr[RANGE][RANGE];
}MazeType;

typedef int directiveType;

typedef struct
{
    int step;
    PosType seat;
    directiveType di;
}ElemType;

typedef struct NodeType
{
    ElemType data;
    struct NodeType *next;
}NodeType,*LinkType;

typedef struct
{
    LinkType top;
    int size;
}Stack;

void   InitStack(Stack  &S)   
{   
    S.top=NULL;   
    S.size=0;   
}   
Status   MakeNode(LinkType &p,ElemType   e)   
{   
    p=(NodeType *)malloc(sizeof(NodeType));   
    if(!p)return   FALSE;   
    p->data=e;
    p->next=NULL;   
    return   TRUE;   
}

Status   Push(Stack   &S,ElemType   e)   
{   
    LinkType   p;   
    if(MakeNode(p,e))   
    {   
        p->next=S.top;   
        S.top=p;   
        S.size++;   
        return   TRUE;   
    }   
    return   FALSE;   
}

Status   StackEmpty(Stack   S)   
{   
    if(S.top==NULL)
        return   TRUE; 
    return  FALSE;   
}  

Status   Pop(Stack   &S,ElemType   &e) 
{
    LinkType   p;
    if(StackEmpty(S)) 
        return   FALSE; 
    else
    { 
        p=S.top;
        S.top=S.top->next; 
        e=p->data; 
        S.size--; 
        free(p);
        return   TRUE;
    }           
}   

Status   pass(MazeType   maze,PosType   curpos)   
{   
    int   m,n;   
    m=curpos.r;   
    n=curpos.c;   
    if(maze.arr[m][n]==' ')
        return   TRUE;   
    return   FALSE;   
}

Status   Same(PosType   curpos,PosType   end)   
{   
    if(curpos.r==end.r && curpos.c==end.c)
        return   TRUE;   
    return   FALSE;   
}

void   FootPrint(MazeType   &maze,PosType   curpos)   
{   
    int   m,n;   
    m=curpos.r;   
    n=curpos.c;   
    maze.arr[m][n]='*';   
}

PosType   NextPos(PosType  curpos,int   di)   
{   
    switch(di)
    {
    case 1:
        curpos.c++; 
        break;        
    case 2:
        curpos.r++; 
        break;
    case 3:
        curpos.c--; 
        break;        
    case 4:
        curpos.r--;   
        break;
    }    
    return   curpos;      
} 

void  MarkPrint(MazeType &maze,PosType p)   
{   
    maze.arr[p.r][p.c]='@';   
}

void  PrintMaze(MazeType   ma)   
{ 
    int i,j;
    printf("\n"); 
    for(i=0;i<ma.m;i++)   
    {   
        printf("\t");
        for(j=0;j<ma.n;j++)   
        {   
            printf("%c ",ma.arr[i][j]);   
        }   
        printf("\n");   
    } 
    printf("\n"); 
} 


void   InitMaze(MazeType  &maze,int  a[][N],int row,int col)   
{   
    int i,j;
    maze.m=row;
    maze.n=col;    
    for(i=0;i<row;i++)   
        for(j=0;j<col;j++)   
        {   
            if(a[i][j]==0)
                maze.arr[i][j]=' '; 
            else
                maze.arr[i][j]='#';   
        }   
} 

Status   MazePath(MazeType   &maze,PosType   start,PosType   end)   
{   
    Stack   s;   
    int   curstep=1;   
    Status   found=FALSE;   
    ElemType   e;   
    PosType   curpos=start; 
    InitStack(s);
    do{   
        if(pass(maze,curpos))   
        {   
            FootPrint(maze,curpos);   
            {   
                e.step=curstep;   
                e.seat=curpos;   
                e.di=1;   
            }   
            Push(s,e);   
            if(Same(curpos,end))
            {
                found=TRUE;
            }
            else
            {   
                curpos=NextPos(curpos,1);   
                curstep++;   
            }   
        }   
        else   
            if(!StackEmpty(s))   
            {   
                Pop(s,e);   
                while((e.di==4) && !StackEmpty(s))
                {   
                    MarkPrint(maze,e.seat);   
                    Pop(s,e);   
                    curstep--;   
                }   
                if(e.di<4)
                {   
                    e.di++;   
                    Push(s,e);   
                    curpos=NextPos(e.seat,e.di);   
                }   
            }   
    }while(!StackEmpty(s) && !found);   
    return   found;   
}  
void Print(int maze[][N])
{
    int i,j;
    printf("表示迷宫的数组\n");
    for(i=0;i<M;i++)
    {
        printf("\t");
        for(j=0;j<N;j++)
        {
            printf("%d ",maze[i][j]);
        }
        printf("\n");
    }
    printf("\n");
}
void main()
{
       
       int maze[M][N]={
           1,1,1,1,1,1,1,1,1,1,1,
               1,0,1,0,0,1,1,1,0,0,1,
               1,0,0,0,0,0,1,0,0,1,1,
               1,0,1,1,1,0,0,0,1,1,1,
               1,0,0,0,1,0,1,1,0,1,1,
               1,1,0,0,1,0,1,1,0,0,1,
               1,1,1,0,0,0,1,0,0,0,1,
               1,1,1,1,1,1,1,1,1,1,1};
           MazeType L;
           PosType   start,end;
           Print(maze);
           InitMaze(L,maze,M,N);
           start.r=1;
           start.c=1;
           end.r=6;
           end.c=9;
           printf("由数组转化出的迷宫");
           PrintMaze(L);
           if(MazePath(L,start,end))
               printf("迷宫的路径，用*表示");
           else
               printf("此迷宫没有通路！");
           PrintMaze(L);
}