渔人过河.cpp

“渔人过河”是数据结构里面很常见的一个课题。要求是找出最好路径

#include<stdio.h>

 struct Situation {
    int farmer;
    int wolf;
    int sheep;
    int cabbage;
};

struct  Situation conditions [20];
char* action[50];
//-------------------------------------------------------------------------//
void init()              //  这里应该就是初始化，说明初始状态，四者都是在南岸
{
    conditions[0].farmer = 0;
    conditions[0].wolf   = 0;
    conditions[0].sheep  = 0;
    conditions[0].cabbage= 0; 
}

//-------------------------------------------------------------------------//
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 showPath(int i)
{
    int c;
    printf("\n\n结果是：\n");
    for(c=0; c<i; c++)
    {
      //cout<<c+1<<action[c]<<endl;    //这里的action[]肯定把路径给存下来了。
      printf("%d:%s\n",c,action[c]);
    }
      printf("狼，羊，白菜都到了对岸!");
    }
//-------------------------------------------------------------------------------------//
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，所有的东东都安全过河了！
        showPath(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()
{
   
	init();
    doStep(0);
	printf("\n");
}

//------------------------------------------------------------------------------//