#include<stdio.h>
#include<stdlib.h>
#define M 4
#define N 4
#define MaxSize 100
int mg1[M+2][N+2]={
    {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,0,0,0,0,1},
    {1,1,1,1,1,1}
};
struct
{
    int i;
    int j;
    int pre;
}Qu[MaxSize];
int front=-1,rear=-1;
int minlen=0;
int num=1;
void print1(int front)
{
    int k=front,j;
    int ns=0;
    do
    {
        j=k;
        k=Qu[k].pre;
        ns++;
    } while(k!=-1);
    if(num==1) minlen=ns;
    if(ns==minlen)
    {
        ns=0;
        k=front;
        printf("第%d条最短路径（反向输出）:\n",num++);
        do
        {
            j=k;
            printf("\t(%d,%d)",Qu[k].i,Qu[k].j);
            k=Qu[k].pre;
            if(++ns%5==0) printf("\n");
        } while(k!=-1);
        printf("\n");
    }
}
void mgpath1(int x1,int y1,int x2,int y2)
{
    int i,j,find=0,di,k;
    rear++;
    Qu[rear].i=x1;
    Qu[rear].j=y1;
    Qu[rear].pre=-1;
    while(front!=rear)
    {
        front++;
        for(di=0;di<4;di++)
        {
            switch(di)
            {
            case 0:i=Qu[front].i-1;j=Qu[front].j;break;
            case 1:i=Qu[front].i;j=Qu[front].j+1;break;
            case 2:i=Qu[front].i+1;j=Qu[front].j;break;
            case 3:i=Qu[front].i;j=Qu[front].j-1;break;
            }
            if(i>0&&j>0&&mg1[i][j]==0&&(i!=Qu[Qu[front].pre].i||j!=Qu[Qu[front].pre].j))
            {
                rear++;
                Qu[rear].i=i;
                Qu[rear].j=j;
                Qu[rear].pre=front;
            }
        }
    }
    for(k=0;k<=rear;k++)
    {
        if(Qu[k].i==x2&&Qu[k].j==y2)
        {
            find=1;
            print1(k);
        }
    }
    if(!find)
        printf("不存在路径!\n");
}
void main()
{
    printf("所有迷宫([1,1]->[4,4])最短路径\n");
    mgpath1(1,1,M,N);
}