#include
#include
#include
#include
#include
?
using?namespace?std;
?
//?過河者，共4種對象
enum?Wader
{
????cabbage????????//?默認(rèn)為0
????goat????????????//?默認(rèn)為1
????wolf????????????//?默認(rèn)為2
????farmer????????????//?默認(rèn)為3???
};
?
//?過河狀態(tài)類型，4bit分別對應(yīng)4種過河對象
typedef?bitset<4>?bitvec;
?
//?判斷狀態(tài)是否安全
bool?is_safe（?const?bitvec&）;
//?判斷待過河的對象是否與農(nóng)夫在河的同一側(cè)
bool?withFarmer（int?bitvec&?）;
?
//?求解得到可行性路徑
void?findRoute（vector?&?path）
{
????//?待發(fā)現(xiàn)的各個狀態(tài)
????queue?discovering;???
????//?過河的初始狀態(tài)為?0000
????discovering.push（0x00）;???
????//?初始狀態(tài)路徑初始化
????path[0]=0;
????//?只要還有下一個狀態(tài)可以到達(dá)，并且尚未到達(dá)最終狀態(tài)
????while?（!discovering.empty（）?&&?（path[15]?==?-1））
????{???
????????//?獲取當(dāng)前待發(fā)現(xiàn)狀態(tài)
????????//?隱式類型轉(zhuǎn)換：int?->?bitset<4>
????????bitvec?curState?=?discovering.front（）;
????????//?隊(duì)首元素彈出
????????discovering.pop（）;
????????//?農(nóng)夫到河對岸，伴隨農(nóng)夫的對象
????????//?依次嘗試?yán)恰撞恕⒀?br/>????????for?（int?companion?=?0;?companion?<=?3;?++companion）???
????????{
????????????//?隨農(nóng)夫過河的只能是與農(nóng)夫在同一河邊的
????????????if?（withFarmer（companioncurState））
????????????{
????????????????//?農(nóng)夫過河后的新狀態(tài)
????????????????bitvec?nextState?=?curState;
????????????????//?農(nóng)夫必定過河
????????????????nextState.flip（farmer）;
????????????????//?如果不是農(nóng)夫單獨(dú)過河的情形
????????????????if（companion?!=?farmer）???????????????????
????????????????????nextState.flip（companion）;
????????????????//?將狀態(tài)矢量轉(zhuǎn)換為整型以作為隊(duì)列元素和路徑下標(biāo)
????????????????int?nextIndex?=?nextState.to_ulong（）;
????????????????//?如果新狀態(tài)是安全的，并且尚未被發(fā)現(xiàn)，
????????????????//?則新狀態(tài)進(jìn)入下一狀態(tài)隊(duì)列
????????????????if?（is_safe（nextState）?&&?（?path[nextIndex]?==?-1）?）
????????????????{
????????????????????//?建立當(dāng)前狀態(tài)與下一狀態(tài)的聯(lián)系
????????????????????path[nextIndex]?=?curState.to_ulong（）;
????????????????????//?將新狀態(tài)入對列
????????????????????discovering.push（nextIndex）;
????????????????}//end?if
????????????}//?end?if
????????}//end?for
????}//?end?while
????//?狀態(tài)起點(diǎn)，沒有前驅(qū)，設(shè)為-1；
????//path[0]?=?-1;
}
?
//?顯示實(shí)際方案
//?從抽象狀態(tài)變量轉(zhuǎn)換為具體表達(dá)
void?displayRoute（const?vector&?path）
{
????//?如果“1111”狀態(tài)沒有前驅(qū)
????//?則沒能夠成功到達(dá)目的狀態(tài)
????if?（path[15]?==?-1）
????{
??????