题解 | #农夫、羊、菜和狼的故事#

#include<iostream>
#include<vector>
#include<string>
#include<cmath>
#include<string.h>
using namespace std;

string item[4] = {"nothing", "wolf", "sheep", "vegetable"};
string act[2] = {"_come", "_go"};
vector<string>v;//存储一次成功的结果
vector<vector<string> > result;//存储多次成功的结果
//数字0-15代表各种状态,对应0000-1111
short int state[16];//state存储是否已经访问过,避免回路

bool isValid(string s) {//s={农夫,狼,羊,蔬菜},0表示在这边,1在岸那边
    if (s[1] == s[2] && s[1] != s[0]) return false;
    if (s[2] == s[3] && s[2] != s[0]) return false;
    return true;
}
//4位二进制->int
int er_int(string s) {
    int x = 0;
    for (int i = 0; i < 4; i++) {
        x += (s[3 - i]-'0') * pow(2, i);
    }
    return x;
}

//int->4位二进制
string int_er(int number) {
    string s = "";
    int count = 4;
    while (count--) {
        s = to_string(number % 2) + s;
        number = number / 2;
    }
    return s;
}
//1->0,0->1
char change(char x){
    if(x=='0')return '1';
    else return '0';
}
//移动
void move(string& s, int i) {
    s[0] = change(s[0]); //农夫移动
    switch (i) {
        case 0://只农夫行动
            break;
        default:
            s[i]=change(s[i]);
    }
    return;
}
void solve(int x) {
    if (x == 15) {//成功
        result.push_back(v);
        return;
    }
    for (int i = 0; i < 4; i++) {
        string s = int_er(x);
        move(s, i);
        int y = er_int(s);
        if (isValid(s) && state[y] == -1) {
            state[y] = x;
            v.push_back((item[i]+act[s[0]-'0']));
            solve(y);
            //回溯
            state[y] = -1;
            v.pop_back();
        }
    }
}


int main() {
    memset(state,-1,sizeof(state));
    state[0]=0;
    solve(0);
    for(int i=0;i<result.size();i++){
        for(int j=0;j<result[i].size();j++){
            cout<<result[i][j]<<endl;
        }
        cout<<"succeed"<<endl;
    }
    
}