浅显的一种方法

#include<iostream>
#include<vector>
#include<set>

using namespace std;

int arry[4]={0};//0代表农夫，1代表羊，2代表菜，3代表狼；元素0代表在河这边，元素1代表在河那边；
vector<string>myvector;//存储操作，全部过河后输出所有操作；
set<string>state;//记录已经遍历过的状态防止重复遍历陷入死循环；
bool flag=false;//去掉flag的地方可以输出另外一种方案，为了通过提交加的；

bool Isvalid(string &str){
    if(arry[1]==arry[2]&&arry[1]!=arry[0])return false;
    if(arry[1]==arry[3]&&arry[1]!=arry[0])return false;
    if(state.find(str)!=state.end())return false;
    return true;
}

string item[4]={"nothing","sheep","vegetable","wolf"};
string act[2]={"_go","_come"};

string Buildstate(){
    string answer="";
    for(int i=0;i<4;++i)answer+=to_string(arry[i]);
    return answer;
}

void solve(int x){//参数x表示当前的目的地，通过1-x可以来回变换目的地；
    if(arry[0]==1&&arry[1]==1&&arry[2]==1&&arry[3]==1){
        for(int i=0;i<myvector.size();i++){
            cout<<myvector[i]<<endl;
        }
        flag=true;
        cout<<"succeed"<<endl;
        return;
    }
    for(int i=0;i<4;i++){
        if(arry[i]==x)continue;//已经在目的地的对象直接跳过，不能被农夫带过河；
        arry[0]=x;//农夫过河
        arry[i]=x;//带的东西过河，i是0时表示农夫自己一个人过河；
        string newstate=Buildstate();
        if(Isvalid(newstate)){//判断有效性
            state.insert(newstate);//更新已经遍历的状态
            myvector.push_back(item[i]+act[1-x]);//字符串拼接，act的表写反了懒得改了
            solve(1-x);
            if(flag)return;
            myvector.pop_back();//回溯
            state.erase(newstate);
            arry[0]=1-x;
            arry[i]=1-x;
        }else{
            arry[0]=1-x;//回溯
            arry[i]=1-x;
        }
    }
}

int main(){
    solve(1);
    return 0;
}