#include<stdio.h>
#include<malloc.h>
#define Maxsize 100
#define NULL 0

typedef struct         //定义迷宫
{
    int arry[Maxsize][Maxsize];   
    int max_x,max_y;            
}sd;

typedef struct point        
{
    int vex_x,vex_y;        
    struct point *next;   
    int direction;         
}Point;

sd create()         
{
    int i,j,x;
    sd a;
    printf("Enter row and lie:");
    scanf("%d  %d",&a.max_x,&a.max_y);   
    printf("提示：请输入0或1，其中0表示通路，1表示不通\n");
    for(i=1;i<=a.max_x;i++)
    {
        printf("enter %d row, (please enter %d datas):",i,a.max_y);
        for(j = 1;j<= a.max_y;j++)
        {
            scanf("%d",&a.arry[i][j]);
        }
    }
    return a;
}


int found(int x,int y,Point *head)  
{
    Point *p = head;
    while(p!=NULL)
    {
        if(x==p->vex_x&&y==p->vex_y)
        return 1;
        p=p->next;
    }
    return 0;
}


Point *secret(sd a)  
{
    Point *top,*p;   
    int i,j,m,x,y;
    p = (Point*)malloc(sizeof(Point));  
    p->vex_x-1;p->vex_y=1;p->next=NULL;
    top=p;        
    j=1;        
    do{
        while(j<=4)
        {
            m=0;  
            x=top->vex_x;
            y=top->vex_y;
            switch(j)
            {
                case 1:   
                    if(y+1<=a.max_y&&!a.arry[x][y+1]&&!found(x,y+1,top))
                    {
                        p=(Point*)malloc(sizeof(Point));
                        p->vex_x=x;p->vex_y=y+1;p->next=top;
                        top->direction=j;
                        top=p;
                        m=1;
                    }
                    break;
                case 2:
                    if(x+1<=a.max_x&&!a.arry[x+1][y]&&!found(x+1,y,top))
                    {
                        p=(Point*)malloc(sizeof(Point));
                        p->vex_x=x+1;p->vex_y=y;p->next=top;
                        top->direction=j;
                        top=p;
                        m=1;
                    }
                    break;
                case 3:
                    if(y-1>1&&!a.arry[x][y-1]&&!found(x,y-1,top))
                    {
                        p=(Point*)malloc(sizeof(Point));
                        p->vex_x=x;p->vex_y=y-1;p->next=top;
                        top->direction=j;
                        top=p;
                        m=1;
                    }
                    break;
                case 4:
                    if(x-1>=1&&!a.arry[x-1][y]&&!found(x-1,y,top))
                    {
                        p=(Point*)malloc(sizeof(Point));
                        p->vex_x=x-1;p->vex_y=y;p->next=top;
                        top->direction=j;
                        top=p;
                        m=1;
                    }
                    break;
            }
            if(m!=0)  
                {j=1;break;}
              else
                j++;  
            }
        if(j>4)  
        {
            if(top!=NULL)   
            {
                top=top->next;j=top->direction+1;top->direction=j;
            }
            else return NULL;   
        }
    }while(top->vex_x!=a.max_x||top->vex_y!=a.max_y);
    return top;
}

void disp(Point *po)
{
    int i=0,top=0;
    Point *stack[Maxsize];
    if(po==NULL)
        printf("NO ROAD!\n");
    else
    {
        while(po!=NULL)
        {
            stack[top++]=po;
            po=po->next;
        }
        while(top>0)
        {
            top--;
            printf("（%d,%d,%d）",stack[top]->vex_x,stack[top]->vex_y,stack[top]->direction);
            i++;
            if(i%8==0)
                printf("\n");
        }
    }
    printf("\n");
}

 main()
{
    sd road;
    Point *po;
    road=create();
    po=secret(road);
    disp(po);
    getchar();
}