第6週目--データ構造の自己構築アルゴリズムライブラリの迷宮問題(キューで)

/**データ構造--迷宮問題(キューで)*Copyright(c)2015煙台大学コンピュータと制御工学学院*All right reserved.*ファイル名:list.cpp*タイトル:迷宮問題(キューで)*分類:キュー*writer:羅海員*date:2015年10月18日*バージョン:V 1.0.1*オペレーティングシステム:windows 8*実行環境:codeblocks*問題説明:
*/

#include <stdio.h>
#define MaxSize 100
#define M 8
#define N 8
int mg[M+2][N+2]=
{
    {1,1,1,1,1,1,1,1,1,1},
    {1,0,0,1,0,0,0,1,0,1},
    {1,0,0,1,0,0,0,1,0,1},
    {1,0,0,0,0,1,1,0,0,1},
    {1,0,1,1,1,0,0,0,0,1},
    {1,0,0,0,1,0,0,0,0,1},
    {1,0,1,0,0,0,1,0,0,1},
    {1,0,1,1,1,0,1,1,0,1},
    {1,1,0,0,0,0,0,0,0,1},
    {1,1,1,1,1,1,1,1,1,1}
};
typedef struct
{
    int i,j;            //     
    int pre;            //               
} Box;                  //    
typedef struct
{
    Box data[MaxSize];
    int front,rear;     //         
} QuType;               //       

void print(QuType qu,int front) //   qu     
{
    int k=front,j,ns=0;
    printf("
");
    do              //        ,         pre     -1
    {
        j=k;
        k=qu.data[k].pre;
        qu.data[j].pre=-1;
    }
    while (k!=0);
    printf("      :
");
    k=0;
    while (k<=front)  //     pre -1   ,        
    {
        if (qu.data[k].pre==-1)
        {
            ns++;
            printf("\t(%d,%d)",qu.data[k].i,qu.data[k].j);
            if (ns%5==0)
                printf("
");   //    5       
        }
        k++;
    }
    printf("
");
}
int mgpath(int xi,int yi,int xe,int ye)                 //     :(xi,yi)->(xe,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;  //(xi,yi)  
    qu.data[qu.rear].pre=-1;
    mg[xi][yi]=-1;                  //    -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);         //  print      
            return(1);              //         1
        }
        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;        //    -1,          
            }
        }
    }
    return(0);                      //          1
}
int main()
{
    mgpath(1,1,M,N);
    return 0;
}

迷宮の例: