这几天碰到一个有意思的程序，讲的是狼 羊 白菜船夫要过河（从南岸到北岸）， 结果每次船只能载船夫和一个东西 ，而且如果船夫不在场的话，狼会偷偷吃掉羊 ，羊会偷偷吃掉白菜 ，自己写一个算法求出可行的方案。。。
首先我的想法是 ，用四个位表示这四个 ，然后位为0表示在南岸，1表示在北岸。
先定义
const int man=8; //1000
const int wolf=4; //0100
const int sheep=2; //0010
const int cabbage=1; //0001
const int origon=0;//0000 means all are on south
const int ok=15;//1111 means all are on north
可以见到，过河时和返回时，能够带的东西，他们的表示方法不一样，比如过河是，位为0的才能过河变成1,同样，返回的时候，位为1的才能变成0，所以还要定义一个标志 1表示过河 0表示返回。
static bool flag=1;
这样我们用一个数字，就能表示出所有事物的状态。题目中给出，狼羊，羊白菜不能一起，不能一起的情况共有四种，南岸北岸，分别是0011（3），1100（12），0110（6），1001（9）
，因为错误情况比较少，我就不使用数组了，直接在预判情况时比较好了。
到现在，我们有了一个筛选条件，就是当前状态不能等与上述四种情况，同时为了避免船夫来回空跑，或者狼羊在两岸，船夫带着白菜来回不停的跑，我还添加一个筛选条件就是状态不能重复，所以添加了一个数组states[]来保存已经经历的状态。
static int *states=new int[10]{222};
由于还要向数组写入，所以定义一个写指针
static int *p=states;
.这时候开始写函数，一共有三个函数，moveto函数输入当期状态和标志，moveto函数通过调用search函数挨个试一下可能出现的情况是否符合标准，如何返回状态，不符合返回-1。
searc函数接受当前状态以及要过河的东西，测试过河侯是否是错误情况以及过河后是否出现重复状态，如果可以过河，输出当前过河的东西以及是过河还是回来。
find函数调用moveto实现过河。
源码及附件如下
#include <iostream>
using namespace std;
const int man=8; //1000
const int wolf=4; //0100
const int sheep=2; //0010
const int cabbage=1; //0001
const int origon=0;//0000 means all are on south
const int ok=15;//1111 means all are on north
static bool flag=1;
static int *states=new int[10]{222};
static int *p=states;
int moveto(int ,int , bool);
int find(int ,int , bool);
int search(int );
int moveto(int nowstate, int x,bool flag)
{
if(flag)
{
x=nowstate|8|1;
if(search(x)!=-1)
{
cout<<“白菜”<<“过河”<<endl;
return x;
}
x=nowstate|8|2;
if(search(x)!=-1)
{
cout<<“羊”<<“过河”<<endl;
return x;
}
x=nowstate|8|4;
if(search(x)!=-1)
{
cout<<“狼”<<“过河”<<endl;
return x;
}
x=nowstate|8;
if(search(x)!=-1)
{
cout<<“只有船夫”<<“过河”<<endl;
return x;
}
} else{
x=nowstate&7&14;
if(search(x)!=-1)
{
cout<<(nowstate-x==8?”农夫”:(nowstate-x==9?”农夫白菜”:(nowstate-x==10?”农夫羊”:”农夫狼”)))<<“回来”<<endl;
return x;
}
x=nowstate&7&13;
if(search(x)!=-1)
{
cout<<(nowstate-x==8?”农夫”:(nowstate-x==9?”农夫白菜”:(nowstate-x==10?”农夫羊”:”农夫狼”)))<<“回来”<<endl;
return x;
}
x=nowstate&7&9;
if(search(x)!=-1)
{
cout<<(nowstate-x==8?”农夫”:(nowstate-x==9?”农夫白菜”:(nowstate-x==10?”农夫羊”:”农夫狼”)))<<“回来”<<endl;
return x;
}
x=nowstate&7;
if(search(x)!=-1)
{
cout<<(nowstate==15?”结束谁也不用”:(nowstate-x==8?”农夫”:(nowstate-x==9?”农夫白菜”:(nowstate-x==10?”农夫羊”:”农夫狼”))))<<“回来”<<endl;
return x;
}
}
}
int search(int state)
{
int *q=states;
if(state==3|state==6|state==9|state==12|state==4)
{
return -1;
}
for(int i=0;i<10;i++)
{
if(state==states[i])
return -1;
}
return state;
}
int find(int nowstate, int x,bool flag)
{
cout<<“now\t”<<nowstate<<endl;
int nextstate=moveto(nowstate,0,flag);
if(nowstate==15)
{
cout<<“结束”<<endl;
*++p=15;
return -1;}
if(nextstate==-1)
{
return -1;
}
else
{
*++p=nextstate;
find(nextstate,0,!flag);
}
}
int main() {
std::cout << “Hello, World!” << std::endl;
*p=0;
find(0,0,1);
return 0;
附件：
https://pan.baidu.com/s/1bpxnrKr
