#include<bits/stdc++.h>using namespace std;vector< pair<int,int> > path;map< vector<int> ,int > vis;void dfs(int La,int Lb,int Ra,int Rb,int flag)// La 左边的好人数 Lb左边的坏人数 flag是左边操作还是右边{if( (Lb>La&&La) || (Rb>Ra&&Ra) ){return;} if( (La+Lb) ==6){for(int i=0;i<path.size();i++){if(i%2==0) cout<<"右->左"<<" ";else cout<<"左->右"<<" ";cout<<path[i].first<<" "<<path[i].second<<endl;}cout<<endl;return;}if(flag)//左边到右边{if(Ra>0) //一个好人{vector<int> s;s.push_back(Ra-1),s.push_back(Rb),s.push_back(0);//0代表左if(!vis[s]) {path.push_back({1,0});vis[s]=1;dfs(La+1,Lb,Ra-1,Rb,0);path.pop_back();}}if(Ra>=2)//两个好人{vector<int> s;s.push_back(Ra-2),s.push_back(Rb),s.push_back(0);if(!vis[s]) {path.push_back({1,1});vis[s]=1;dfs(La+2,Lb,Ra-2,Rb,0);path.pop_back();}}if(Rb>0) //一个坏人{vector<int> s;s.push_back(Ra),s.push_back(Rb-1),s.push_back(0);if(!vis[s]) {path.push_back({-1,0});vis[s]=1;dfs(La,Lb+1,Ra,Rb-1,0);path.pop_back();}}if(Rb>=2)//两个坏人{vector<int> s;s.push_back(Ra),s.push_back(Rb-2),s.push_back(0);if(!vis[s]) {path.push_back({-1,-1});vis[s]=1;dfs(La,Lb+2,Ra,Rb-2,0);path.pop_back();}}if(Ra&&Rb)//一个好人一个坏人{vector<int> s;s.push_back(Ra-1),s.push_back(Rb-1),s.push_back(0);if(!vis[s]) {path.push_back({1,-1});vis[s]=1;dfs(La+1,Lb+1,Ra-1,Rb-1,0);path.pop_back();}}}else{if(La>0) {vector<int> s;s.push_back(La-1),s.push_back(Lb),s.push_back(1);if(!vis[s]){path.push_back({1,0});vis[s]=1;dfs(La-1,Lb,Ra+1,Rb,1);path.pop_back();}}if(La>=2){vector<int> s;s.push_back(La-2),s.push_back(Lb),s.push_back(1);if(!vis[s]){path.push_back({1,1});vis[s]=1;dfs(La-2,Lb,Ra+2,Rb,1);path.pop_back();}}if(Lb>0) {vector<int> s;s.push_back(La),s.push_back(Lb-1),s.push_back(1);if(!vis[s]) {path.push_back({-1,0});vis[s]=1;dfs(La,Lb-1,Ra,Rb+1,1);path.pop_back();}}if(Lb>=2){vector<int> s;s.push_back(La),s.push_back(Lb-2),s.push_back(1);if(!vis[s]) {path.push_back({-1,-1});vis[s]=1;dfs(La,Lb-2,Ra,Rb+2,1);path.pop_back();}}if(La&&Lb){vector<int> s;s.push_back(La-1),s.push_back(Lb-1),s.push_back(1);if(!vis[s]) {path.push_back({1,-1});vis[s]=1;dfs(La-1,Lb-1,Ra+1,Rb+1,1);path.pop_back();}}}}int main(void){dfs(0,0,3,3,1);return 0;}
如果觉得《三人三鬼过河(野人与传教士过河)问题c/c++代码》对你有帮助，请点赞、收藏，并留下你的观点哦！
