一个农夫带着一只狼、一只羊和一棵白菜，身处河的南岸。他要把这些东西全部运到北岸。他面前只有一条小船，船只能容下他和一件物品，另外只有农夫才能撑船。如果农夫在场，则狼不能吃羊，羊不能吃白菜，否则狼会吃羊，羊会 吃白菜，所以农夫不能留下羊和白菜自己离开，也不能留下狼和羊自己离开，而狼不吃白菜。请求出农夫将所有的东西运过河的方案。
避免出现重复步骤
//Ex8_8 #include<iostream> #include<vector> #include<map> using namespace std; enum Res { wolf,sheep,greens,null }; map<Res, int> Pass = { {wolf,0},{sheep,0},{greens,0} }; //0表示在左侧，1表示在右侧 vector<pair<map<Res, int>, int>>result = { {Pass,0 } }; bool judge(int i) { if (Pass[wolf]==i&&i == Pass[sheep] || (Pass[sheep] == i && i == Pass[greens])) return false; if (count(result.begin(), result.end(), result.back()) > 1) //避免某种情况再次出现,出现死循环 return false; return true; } void dfs(int i) { //i为0表示从左往右，1为从右到左 if (!judge(!i)) return; if (Pass[wolf]&& Pass[sheep]&& Pass[greens] ) { cout << "-------------------" << endl; for (int i = 0; i < result.size();i++) { cout << (!result[i].first[wolf] ? "狼 " : "") << (!result[i].first[sheep] ? "羊 " : "") << (!result[i].first[greens] ? "菜 " : ""); cout << (result[i].second? " <- " : " -> "); cout << (result[i].first[wolf] ? "狼 " : "") << (result[i].first[sheep] ? "羊 " : "") << (result[i].first[greens] ? "菜 " : ""); cout << endl; } return; } else { if (i){ //当从右往左的时候可以不带东西 result.push_back({ Pass ,!i }); dfs(!i); result.pop_back(); } for (auto& it : Pass) { if (it.second==i) { it.second =!it.second; result.push_back({ Pass ,!i }); dfs(!i); result.pop_back(); it.second = !it.second; } } } } int main() { cout << "箭头所指方向没有捕食关系既能共存：" << endl; dfs(0); return 0; }
