대기 열 에서 미궁 의 가장 짧 은 경 로 를 찾 습 니 다 (모든 시도 상 태 를 포함 하고 미궁 은 무 작위 로 생 성 됩 니 다)

#include
#include
#include
#define Maxsize 50
int mg[10][10];
void shengcheng()
{
    for(int i=0; i<10; i++)
    {
        mg[i][0]=1;
        mg[i][9]=1;
        mg[0][i]=1;
        mg[9][i]=1;
    }
    srand(time(NULL));
    for(int i=1; i<9; i++)
    {
        mg[1][1]=0;
        for(int j=1; j<9; j++)
        {
            mg[i][j]=rand()%2;
            mg[8][8]=0;
        }
    }
    for(int i=0; i<10; i++)
    {
        for(int j=0; j<10; j++)
        {
            printf("%d ",mg[i][j]);
            if(j==9)
                printf("
");
        }
    }
}
typedef struct
{
    int i;
    int j;
    int pre;
} Box;
typedef struct
{
    Box data[Maxsize];
    int front1;
    int rear;
} QuType;
void print(QuType qu,int front2);
bool mgpath1(int xi,int yi,int xe,int ye)
{
    int i,j,find1=0,p,di,o,q;
    QuType qu;
    qu.front1=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][xi]=-1;
    while(qu.front1!=qu.rear&&!find1)
    {
        qu.front1++;
        i=qu.data[qu.front1].i;
        j=qu.data[qu.front1].j;
        o=i;
        q=j;
        printf("    %d,%d     
",i,j);
        if(i==xe&&j==ye)
        {
            find1=1;
            printf("     
");
            print(qu,qu.front1);
            return true;
        }
        for(di=0; di<4; di++)
        {
            switch(di)
            {
            case 0:
                p=0;
                i=qu.data[qu.front1].i-1;
                j=qu.data[qu.front1].j;
                break;
            case 1:
                p=1;
                i=qu.data[qu.front1].i;
                j=qu.data[qu.front1].j+1;
                break;
            case 2:
                p=2;
                i=qu.data[qu.front1].i+1;
                j=qu.data[qu.front1].j;
                break;
            case 3:
                p=3;
                i=qu.data[qu.front1].i;
                j=qu.data[qu.front1].j-1;
                break;
            }
            if(mg[i][j]==0)
            {
                switch(p)
                {
                case 0:
                    printf("    ，    ，   ：%d,%d,         ：%d,%d
",i,j,qu.data[qu.front1].i,qu.data[qu.front1].j);
                    break;
                case 1:
                    printf("    ，    ，   ：%d,%d,         ：%d,%d
",i,j,qu.data[qu.front1].i,qu.data[qu.front1].j);
                    break;
                case 2:
                    printf("    ，    ，   ：%d,%d,         ：%d,%d
",i,j,qu.data[qu.front1].i,qu.data[qu.front1].j);
                    break;
                case 3:
                    printf("    ，    ，   ：%d,%d,         ：%d,%d
",i,j,qu.data[qu.front1].i,qu.data[qu.front1].j);
                    break;
                }
                qu.rear++;
                qu.data[qu.rear].i=i;
                qu.data[qu.rear].j=j;
                qu.data[qu.rear].pre=qu.front1;
                mg[i][j]=-1;
            }
        }
        printf("%d,%d       ！
",o,q);
    }
    return false;
}
void print(QuType qu,int front2)
{
    int k=front2,j;
    printf("
");
    do
    {
        j=k;
        k=qu.data[k].pre;
        qu.data[j].pre=-1;
    }
    while(k!=0);
    printf("      ：
");
    k=0;
    while(k  ",qu.data[k].i,qu.data[k].j);
            mg[qu.data[k].i][qu.data[k].j]=5;
        }
        k++;
    }
    printf("
");
    for(int i=0; i<10; i++)
    {
        for(int j=0; j<10; j++)
        {
            printf("%d  ",mg[i][j]);
            if(j==9)
                printf("
");
        }
    }
    printf("
");
}
int main()
{
    int n;
    printf("1.  
");
    printf("2.  
");
    while(scanf("%d",&n)!=EOF)
    {
        switch(n)
        {
        case 1:
            shengcheng();
            if(!mgpath1(1,1,8,8))
                printf("     ！
");
            break;
        case 2:
            exit(0);
        }
        printf("


");
        printf("1.  
");
        printf("2.  
");
    }
    return 0;
}