程序代码：

#include <stdio.h>
char *name[] = {"农夫","狼","羊","菜"};
char *name1[] = {"去对岸","回本岸"};
struct way
{
    int num;//农夫带走的东西 包括他自己
    bool go_back;//带到那里去0表示去对岸 1表示会本岸
};

bool now[4] = {0};//当前状态0表示在本岸1表示在对岸
bool foot[2][2][2][2] = {0};//状态标记表

bool Kill(bool a,bool b,bool c,bool d)//判断是否会吃掉
{
    if((c == b && a != c) || (d == c && a != c))
        return true;
    return false;
}
bool dfs(way w[],int sumway,bool now[])
{
    if(4 == now[0]+now[1]+now[2]+now[3])//如果都在对岸
    {
        for(int i = 0;i<sumway;i++)
            printf("农夫带着%s%s\n",name[w[i].num],name1[w[i].go_back]);
        printf("\n\n");
        return true;
    }
    int i;
    if(0 == now[0])//如果农夫在本岸
    {
        for(i = 0;i<4;i++)//遍历他所能带走的东西（包括带走他自己）
        {
            if(0 == now[i])
            {
                now[0] = now[i] = 1;//试探
                if(!foot[now[0]][now[1]][now[2]][now[3]])//判断
                {
                    if(!Kill(now[0],now[1],now[2],now[3]))
                    {
                        foot[now[0]][now[1]][now[2]][now[3]] = true;//试探
                        w[sumway].num = i; w[sumway++].go_back = 0;//记录路径                    
                        dfs(w,sumway,now);//继续搜索
                        foot[now[0]][now[1]][now[2]][now[3]] = false;//回溯
                        sumway--;
                    }
                }
                now[0] = now[i] = 0;//回溯
            }
        }
        return false;
    }
    else //如果农夫在对岸 下面注释同上
    {
        for(i = 0;i<4;i++)
        {
            if(1 == now[i])
            {
                now[0] = now[i] = 0;
                if(!foot[now[0]][now[1]][now[2]][now[3]])
                {
                    if(!Kill(now[0],now[1],now[2],now[3]))
                    {
                        foot[now[0]][now[1]][now[2]][now[3]] = true;
                        w[sumway].num = i; w[sumway++].go_back = 1;                    
                        if(dfs(w,sumway,now))
                            return true;
                        foot[now[0]][now[1]][now[2]][now[3]] = false;
                        sumway--;
                    }
                }
                now[0] = now[i] = 1;
            }
        }
        return false;
    }
}

int main()
{
    way w[100] = {0};
    dfs(w,0,now);
    return 0;
}