农夫过河问题-广度优先搜索-逻辑运算

辣鸡小玲的题解
冯向阳老师的数据结构-队列
农夫过河，上题目：

题目

然后贴代码

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <sstream>
using namespace std;
const int MAXLISTSIZE = 100;
template<class ElemType>
class SqQueue
{
private:ElemType *elem;   // 存储空间基址int fronter;   // 队头指针int rearer;   // 队尾指针int maxSize;        // 允许的最大存储容量(以sizeof(ElemType)为单位
public://初始化顺序队列SqQueue(int ms = 20){if(ms==0){ms=MAXLISTSIZE;}elem=new ElemType [ms];if(!elem){cout<<"Fail to get space in SqQueue!"<<endl;exit(0);}maxSize=ms;fronter=0;rearer=0;}//删除顺序队列~SqQueue(){QueueDestroy();}//将顺序队列置为空bool QueueClear(){delete [] elem;elem=new ElemType [maxSize];if(!elem){cout<<"Fail to get space in QueueClear!"<<endl;exit(0);}fronter=0;rearer=0;}//设置顺序栈的长度//bool SetListLength(int len);//返回顺序队列长度int QueueLength(){return rearer-fronter;}//判断顺序队列是否为空bool QueueisEmpty() const{return fronter == rearer;}//判断顺序队列是否为满bool QueueFull() const{return rearer==maxSize;}//用e返回队头元素bool GetFront(ElemType &e){if(!QueueisEmpty()){e=elem[fronter];return true;}cout<<"Queue is empty in GetFront"<<endl;return false;}//入队bool enQueue(const ElemType &e){if(rearer<maxSize){elem[rearer++]=e;return true;}else{if(DoubleSpace())//如果加倍成功{elem[rearer++]=e;return true;}else{cout<<"Fail to DoubleSpace in enQueue"<<endl;return false;}}return true;}//出队bool deQueue(ElemType &e){if(QueueisEmpty()){cout<<"Queue is Empty in deQueue"<<endl;return false;}e=elem[fronter++];return true;}//销毁顺序队列bool QueueDestroy(){delete [] elem;fronter=0;rearer=0;return true;}//顺序队列最大存储空间加倍bool DoubleSpace(){ElemType *newElem;maxSize*=2;newElem= new ElemType [maxSize];if(!newElem){cout<<"Fail to get space in DoubleSpace"<<endl;return false;}for(int i=0; i<maxSize/2; i++){newElem[i]=elem[i];}elem=newElem;return true;}
};
//位向量从低位到高位分别代表羊、白菜、狼、农夫
//0000代表都在南岸，1111代表都在北岸
enum {GOAT=1,CABBAGE=2,WOLF=4,FARMER=8};//MARK I
//求人或物当前状态的函数
bool goat(int st)//MARK II
{return (st&GOAT)!=0;
}
bool cabbage(int st)
{return (st&CABBAGE)!=0;
}
bool wolf(int st)
{return (st&WOLF)!=0;
}
bool farmer(int st)
{return (st&FARMER)!=0;
}
//安全判断函数，如果安全则返回true
bool safe(int st)//MARK III
{if((goat(st)==cabbage(st))&&(goat(st)!=farmer(st)))return false;//羊吃白菜if((goat(st)==wolf(st))&&(goat(st)!=farmer(st)))return false;//狼吃羊return true;
}
template<class ElemType>
void farmerProblem(SqQueue<ElemType> &S)//MARK IV
{int mover,st,st_new;int route[16]= {0,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1};S.enQueue(0);while(!S.QueueisEmpty()&&route[15]==-1)//队列不空且未到达末了状态{S.deQueue(st);for(mover=1; mover<=8; mover<<=1) //mover指狼、菜、羊{if(farmer(st)==(0!=(st&mover)))//与农夫同岸？{//逻辑与：&   全1为1//逻辑或：|   有1为1//逻辑异或：^ 一0一1为1st_new=st^(FARMER|mover);//求过河后的状态if(route[st_new]==-1&&safe(st_new)){//新状态没到过且安全，记录路径并入队列route[st_new]=st;S.enQueue(st_new);}}}}//打印输出string pri[16]= {"0000","0001","0010","0011","0100","0101","0110","0111","1000","1001","1010","1011","1100","1101","1110","1111"};int i=15;while(i!=0){cout<<pri[i]<<endl;i=route[i];}cout<<"0000"<<endl;
}
int main()
{SqQueue<int> A;farmerProblem(A);return 0;
}

MARK I 143行enum枚举

这个枚举设计得很精妙噢，在一个字节的二进制里，0001，0010，0100，1000对应十进制就是1，2，4，8，把羊、菜、狼、人和一个数关联起来，以便后面可以用各种逻辑运算符做运算。

MARK II 145-160行状态函数

传进来的这个st表示当前的状态，题目里用0表示某物在南岸，1表示某物在北岸，比如1001就表示，人和羊在北岸，狼和菜在南岸。
逻辑与&：全1为1
比如st=0101（狼和羊在北岸，人和菜在南岸）去逻辑与羊，那结果就是
0101&0001=0001，调用goat(st)函数得到的返回值就是true，这就代表st状态下，羊在北岸；同样的你可以用st逻辑与人，0101&1000=0000，调用farmer(st)的返回值就是false，表示st状态下，人在南岸。
这样，用逻辑运算符就可以得到某个物品在st状态下在南岸还是北岸了。

MARK III 162-169行安全判断函数

上面说了逻辑与，再看164行的第一个if，如果在st状态下羊、菜同岸且羊、人不同岸，那狼会把羊吃了，所以不安全，return false；第二个if同理。除了两个if的状态，其他状态都是安全的。

MARK IV 171-195行 广度优先搜索

174行是用一个数组标记路线、记录路线，跳转到190行去看，把st存到下标为new_st的数组位置中，具体原理，MARK V里面讲。第一个结点存储0000，其他点都赋值成-1，表示没有探索过。
和深度优先搜索不太一样，深度优先搜索是用栈来存储结点，而广度优先搜索用队列，并且队列里是不留东西的（除了最后一个结点，遇到它的时候就是跳出循环的时候），这就要求用其他的数据结构来存储路径，这题里用了数组。
176判定循环条件，因为这题简单农夫问题是必定有解的，所以我们只要把这个解求出来就行，不用考虑无解的情况。
178，取出队列头的结点，进for循环。mover<<=1是左移运算符(移1位），相当于*2（0001->0010)，是对当前状态，狼、菜、羊能否过河的遍历，能过河，就过去，且新状态往队列里放。
写着写着发现一个好玩的问题噢
初始状态：0000 四件物品都在南岸
第一步：人和羊过河 0000->1001
第二步：人回去南岸 1001->0001
第三步：人带菜/狼过河 0001->1011
--------------------------------0001->1101
显然，第三步带狼/菜过河都是可以的，但是输出中是选择了带菜过河
这是因为，当mover位移到0010的时候，发现可以带菜过河，于是农夫就把菜带过河了，这个操作搞完以后，农夫就在对岸了，就和狼不在同一边了。
还有第二步，代码中是怎么实现，人回去而不带羊回去的？
1.人羊一起回去的话，会因为route数组标记过而进不去187行的if
2.mover=8的时候就是人自己回去对岸的情况

MARK V 190行 路径存储

代码：route[st_new]=st 的解释
route数组里，探索过的路径会存下前后关联的两个状态，比如说，前一个状态是0000（初始），下一个状态是1001（农夫带羊过河），那数组route里，route[1001]的位置（就是route[9])就会存0000，也就是route[9]=0；
这样，打印路径的时候（196-205行），我只要初始让i=15，然后打印i，更新的时候，让i=route[i]，就会转到前一个状态去，一直打印一直转到前一个状态，等到i=0的时候跳出循环就可以完成路径打印了。