#include<stdio.h>
#include<malloc.h>
typedef int DataType;
typedef struct node{
    DataType data;//节点的数据域
    struct node * next; 
}Node;
typedef struct{
    Node *front,*rear;
}LinkQueue;
//有头节点初始化
LinkQueue * initQueue(){
    LinkQueue *q = (LinkQueue *)malloc(sizeof(LinkQueue));
    Node *head = (Node *)malloc(sizeof(Node));
    head->next = NULL;
    q->front = head;
    q->rear = head;
    return q;    
} 
//空
int isEmpty(LinkQueue *q ){
    return q->front==q->rear;
}
//进队
LinkQueue * enQueue(LinkQueue *q,DataType x){
    //创建一个新节点
    Node *s = (Node*)malloc(sizeof(Node));
    s->data = x;
    s->next = NULL;
    //将s放在rear的next中
    q->rear->next = s;
    //修改rear
    q->rear=s;
    return q; 
}
//出队
LinkQueue *deQueue(LinkQueue *q,DataType *x){
    if(isEmpty(q )){
        printf("队列空，不能出队！");
        return q;
    }
    //获取要删除的节点
    Node *s = q->front->next;
    *x = s->data; 
    printf("%d出队",*x);
    if(s==q->rear) q->rear=q->front;
    //架桥
    q->front->next = s->next; 
    //释放s
    free(s);
    return q; 
}
//取队头
int getFront(LinkQueue *q,DataType *x){
    if(isEmpty(q )){
        printf("队列空，没有队头元素！");
        return 0;
    }
    //获取队头节点点
    Node *s = q->front->next;
    *x = s->data; 
    return 1; 
}
//遍历
void print(LinkQueue *q){
    Node *p = q->front->next;
    while(p){
        printf("%d ",p->data);
        p=p->next;
    }
    printf("\n");
}
int main(){
    int x,n,i;
    LinkQueue *q =  initQueue();
    printf("请输入n:");
    scanf("%d",&n);
    printf("请输入%d个元素",n);
    for(i=0;i<n;i++){
        scanf("%d",&x);
        q = enQueue(q,x);
    }
    print(q);
    printf("请输入出队个数:");
    scanf("%d",&n);
    for(i=0;i<n;i++){
        q = deQueue(q,&x);
        //printf("%d",x);
    }
    printf("还剩下的元素：\n");
    print(q);
    return 0;

}
//迷宫

#include<stdio.h>
#define M 4
#define N 4
#define MaxSize 20
typedef struct 
{      int i,j;     //方块的位置
       int pre;     //本路径中上一方块在队列中的下标
}  Box;         //方块类型
typedef struct
{     Box data[MaxSize];
       int front,rear;  //队头指针和队尾指针
}  QuType;      //定义顺序队类型
typedef struct{
    Box data[MaxSize];
    int top;
}Stack;
int mg[M+2][N+2]=     //M=4,N=4
 { {1, 1, 1, 1, 1, 1},
   {1, 0, 0, 0, 1, 1},
   {1, 0, 1, 0, 0, 1},
   {1, 0, 0, 0, 1, 1},
   {1, 1, 0, 0, 0, 1},
   {1, 1, 1, 1, 1, 1}  };
void print(Stack st){
    while(st.top!=-1){
        printf("(%d,%d) \n",st.data[st.top].i,st.data[st.top].j);
        st.top--;
    }
} 
void BFS(Box in,Box out){
    QuType qu;
    Stack st;
    st.top=-1;
    Box tmp,m,n; 
    int i,j,indx;
    qu.front=qu.rear=-1; 
    //首先把入口压入队列
    qu.data[++qu.rear]=in;
    //地图上标记为-1
    mg[in.i] [in.j]=-1;
    //队列非空
    while(qu.front!=qu.rear){
        //出队
        tmp = qu.data[++qu.front];
        i=tmp.i;
        j=tmp.j;
        if(i==out.i && j==out.j){//找到了出口 
            //输出路径
            indx = qu.front;
            while(qu.data[indx].pre!=-1){
                //printf("(%d,%d) ",qu.data[indx].i,qu.data[indx].j);
                //indx = qu.data[indx].pre;
                st.data[++st.top]=qu.data[indx];
                indx = qu.data[indx].pre;
            } 
            //printf("(%d,%d)\n ",in.i,in.j);
            st.data[++st.top]=qu.data[indx];
            //输出
            print(st) ;
            return;
        }
        //将tmp的相邻能走的box入队，从右-上顺时针方向开始探测
        if(mg[tmp.i][tmp.j+1]==0){
            m.i=tmp.i;
            m.j=tmp.j+1;
            m.pre = qu.front; 
            qu.data[++qu.rear] = m;
            mg[m.i] [m.j]=-1;   
        } 
        if(mg[tmp.i+1][tmp.j]==0){
            m.i=tmp.i+1;
            m.j=tmp.j;
            m.pre = qu.front; 
            qu.data[++qu.rear] = m;
            mg[m.i] [m.j]=-1;   
        } 
        if(mg[tmp.i][tmp.j-1]==0){
            m.i=tmp.i;
            m.j=tmp.j-1;
            m.pre = qu.front; 
            qu.data[++qu.rear] = m;
            mg[m.i] [m.j]=-1;   
        } 
        if(mg[tmp.i-1][tmp.j]==0){
            m.i=tmp.i-1;
            m.j=tmp.j-1;
            m.pre = qu.front; 
            qu.data[++qu.rear] = m;
            mg[m.i] [m.j]=-1;   
        } 
    } 

}

int main(){
    Box in,out;
    in.i=1,in.j=1,in.pre=-1;
    out.i=4,out.j=4,out.pre=-1;
    BFS(in,out);
    return 0;
}