#include <stdio.h>
#include <stdlib.h>

typedef struct OnBoat
{                    //儲存船上的人數
    int businessman;
    int servant;
    struct onBoat *next;
}
*onBoat;

typedef struct OnBank
{                   //儲存岸上人數的鏈表
    int businessman1;
    int servant1;
    int businessman2;
    int servant2;
    int n;
    struct oneSide *back;
}
*onSide;

int sign(int n)                       //返回1或者-1
{
    if (n%2==0)
    {
        return -1;
    }
    return 1;
}


int judge(struct OnBank *p)           //判斷安全點
{
    struct OnBank *p1=p;
    if (p1->businessman1>3) return -1;
    if (p1->servant1>3) return -1;
    if (p1->businessman2>3) return -1;
    if (p1->servant2>3) return -1;

    if (p1->businessman1<0) return -1;
    if (p1->servant1<0) return -1;
    if (p1->businessman2<0) return -1;
    if (p1->servant2<0) return -1;

    if (p1->businessman1!=0)
    {
        if (p1->servant1>p1->businessman1)
        {
            return -1;
        }
    }

    if (p1->businessman2!=0)
    {
        if (p1->servant2>p1->businessman2)
        {
            return -1;
        }
    }

    while (p1!=NULL)
    {
        p1=p1->back;
        if (p1!=NULL)
        {
            if (p1->n%2==p->n%2)
            {
                if (p1->businessman1==p->businessman1)
                {
                    if (p1->businessman2==p->businessman2)
                    {
                        if (p1->servant1==p->servant1)
                        {
                            if (p1->servant2==p->servant2)
                            {
                                return -1;
                            }
                        }
                    }
                }
            }
        }
    }

    if (p->businessman1==0&&p->servant1==0)
    {
        if (p->n%2==0)
        {
            return 1;
        }
        else
        {
            return -1;
        }
    }

    return 0;

}

void copyit(struct OnBank *p3,struct OnBank *p)
{
    p3->businessman1=p->businessman1;
    p3->businessman2=p->businessman2;
    p3->servant1=p->servant1;
    p3->servant2=p->servant2;
    p3->n=p->n+1;
    p3->back=p;

}/*復制內容函數，將p中的內容寫入p3所指向的鏈表單元中*/

void print(struct OnBank *p3)
{
    struct OnBank *p;
    p=p3;
    while (p!=NULL)
    {
        if (p->back==NULL)
        {
            printf("%d,%d::%d,%d\t\n",p->businessman1,p->servant1,p->businessman2,p->servant2);
        }
        else
        {
            printf("%d,%d::%d,%d\t",p->businessman1,p->servant1,p->businessman2,p->servant2);
        }
        p=p->back;
    }

}

void freeit(struct OnBank *p)
{
    struct OnBank *p1=p;
    free(p);
    if (p1!=NULL)
    {
        p1->back=NULL;
    }

}/*釋放該單元格，并將其上的單元格的next指針還原*/



void trans(struct OnBank *p,struct OnBoat *head)
{
    struct OnBank *p3;/*p3為申請的結構體指針*/
    struct OnBoat *fla;
    int i;
    int j;
    int f;

    fla=head;

    p3=(struct OnBank *)malloc(sizeof(struct OnBank));
    f=sign(p->n);
    for (i=0;i<5;i++)
    {
        fla=fla->next;
        copyit(p3,p);
        p3->businessman1-=fla->businessman*f;
        p3->servant1-=fla->servant*f;
        p3->businessman2+=fla->businessman*f;
        p3->servant2+=fla->servant*f;/*運算過程，即過河過程*/
        j=judge(p3);/*判斷，j記錄判斷結果*/
        if (j==-1)
        {
            if (i<5)
            {
                continue;
            }
            else
            {
                freeit(p3);
                break;
            }
        }

        if (j==1)
        {
            if (i<5)
            {
                print(p3);
                continue;
            }
            else
            {
                print(p3);
                freeit(p3);
                break;
            }
        }

        if (j==0)
        {
            trans(p3,head);
        }
    }
}/*轉移函數，即將人轉移過河*/







int main()
{
    int i=0,j=0;
    struct OnBoat *p,*q;
    struct OnBank *p3;

    onBoat head=(struct OnBoat *)malloc(sizeof(struct OnBoat));
    head->businessman=0;
    head->servant=0;
    head->next=NULL;
    p=head;

    for (i=0;i<3;i++)                           //初始化船上人數的鏈表
    {
        for (j=0;j<3;j++)
        {
            if ((i+j)<3)
            {
                if (i==0&&j==0)
                {
                    continue;
                }
                q=(struct OnBoat *)malloc(sizeof(struct OnBoat));
                q->businessman=i;
                q->servant=j;
                p->next=q;
                q->next=NULL;
                p=q;
            }
        }
    }

    p3=(struct OnBank *)malloc(sizeof(struct OnBank));
    p3->back=NULL;
    p3->servant1=3;
    p3->businessman1=3;
    p3->servant2=0;
    p3->businessman2=0;
    p3->n=1;/*設立初始頭指針*/

    trans(p3,head);



    return 0;
}