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