#include <iostream.h>
struct Condition {
    int farmer;
    int wolf;
    int sheep;
    int cabbage;
};
struct Condition conditions [20];
char* action[100];
void takeWolfOver(int i)
{
    action[i] = "把狼带过河.";
    conditions[i+1].wolf=1;
    conditions[i+1].sheep=conditions[i].sheep;
    conditions[i+1].cabbage=conditions[i].cabbage;
}
void takeWolfBack(int i)
{
    action[i] = "把狼带回来.";
    conditions[i+1].wolf=0;
    conditions[i+1].sheep=conditions[i].sheep;
    conditions[i+1].cabbage=conditions[i].cabbage;
}
void takeSheepOver(int i)
{
    action[i] = "把羊带过河.";
    conditions[i+1].wolf=conditions[i].wolf;
    conditions[i+1].sheep=1;
    conditions[i+1].cabbage=conditions[i].cabbage;
}
void takeSheepBack(int i)
{
    action[i] = "把羊带回来.";
    conditions[i+1].wolf=conditions[i].wolf;
    conditions[i+1].sheep=0;
    conditions[i+1].cabbage=conditions[i].cabbage;
}
void takeCabbageOver(int i)
{
    action[i] = "把菜带过去.";
    conditions[i+1].wolf=conditions[i].wolf;
    conditions[i+1].sheep=conditions[i].sheep;
    conditions[i+1].cabbage=1;
}
void takeCabbageBack(int i)
{
    action[i] = "把菜带回来.";
    conditions[i+1].wolf=conditions[i].wolf;
    conditions[i+1].sheep=conditions[i].sheep;
    conditions[i+1].cabbage=0;
}
void getOverBarely(int i)
{
    action[i] = "空手过河.";
    conditions[i+1].wolf=conditions[i].wolf;
    conditions[i+1].sheep=conditions[i].sheep;
    conditions[i+1].cabbage=conditions[i].cabbage;
}
void getBackBarely(int i)
{
   action[i] = "空手返回.";
    conditions[i+1].wolf=conditions[i].wolf;
    conditions[i+1].sheep=conditions[i].sheep;
    conditions[i+1].cabbage=conditions[i].cabbage;
}
void showSolution(int i)
{
    int c;
    cout<<"可以这样安排："<<endl;
    for(c=0; c<i; c++)
    {
      cout<<c+1<<action[c]<<endl;
    }
      cout<<"OK，任务完成了！"<<endl;
    }
void doStep(int i)
{
    int c;
    int j;
    if(conditions[i].farmer==1&&
        conditions[i].wolf==1&&
        conditions[i].sheep==1&&
        conditions[i].cabbage==1)
    {
        //OK，所有的东东都安全过河了！
        showSolution(i);
        return;
    }
    //check for lose.
    if(
        (conditions[i].farmer!=conditions[i].wolf && conditions[i].wolf==conditions[i].sheep)
        ||
        (conditions[i].farmer!=conditions[i].sheep && conditions[i].sheep==conditions[i].cabbage)
    )
    {
        //有问题，狼会吃掉羊，或羊会吃掉菜的！
        return;
    }
     for (c=0; c<i; c++)
    {
        if(conditions[c].farmer==conditions[i].farmer&&
            conditions[c].wolf==conditions[i].wolf&&
            conditions[c].sheep==conditions[i].sheep&&
            conditions[c].cabbage==conditions[i].cabbage)
        {
            //已经过河了，或是全部又返回.
            return;
        }
    }
    
    j=i+1;
    if(conditions[i].farmer==0)    
    {
        conditions[j].farmer=1;
        getOverBarely(i);
        doStep(j);
        if(conditions[i].wolf==0)
        {
            takeWolfOver(i);
            doStep(j);
        }
        if(conditions[i].sheep==0)
        {
            takeSheepOver(i);
            doStep(j);
        }
        if(conditions[i].cabbage==0)
        {
            takeCabbageOver(i);
            doStep(j);
        }
    }
    else
    {
        conditions[j].farmer=0;
        getBackBarely(i);
        doStep(j);
        if(conditions[i].wolf==1)
        {
            takeWolfBack(i);
            doStep(j);
        }
        if(conditions[i].sheep==1)
        {
            takeSheepBack(i);
            doStep(j);
        }
        if(conditions[i].cabbage==1)
        {
            takeCabbageBack(i);
            doStep(j);
        }
    }
}
void main()
{
    cout<<"有一个农夫过河带一条狼、一只羊和一棵白菜过河. "<<endl;
    cout<<"如果没有农夫看管，则狼要吃羊，羊要吃白菜."<<endl;
    cout<<"但是船很小，只够农夫带一样东西过河。"<<endl;
    cout<<"问农夫该如何解此难题？"<<endl;
    conditions[0].farmer = 0;
    conditions[0].wolf   = 0;
    conditions[0].sheep  = 0;
    conditions[0].cabbage= 0;
    doStep(0);
}