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

#include <iostream>
#include<stack>
using namespace std;

int  status[4][2] = {0};
int a[4];
bool f[20][2] = {false};
string Move[2] = {"_come", "_go"};
string item[4] = {"nothing", "wolf", "sheep", "vegetable"};
stack<string>result;
bool check(int x, int d) {
    for (int i = 0 ; i < 4 ; ++ i ) {
        a[i] = status[i][1 - d];
    }
    a[x] = 1 - a[x];
    if (a[1] == 1 && a[2] == 1) return false ;
    if (a[2] == 1 && a[3] == 1) return false ;
    return true ;
}
int getNum() {
    return (status[0][0] << 3) + (status[1][0] << 2) + (status[2][0] << 1) +
           status[3][0];
}
bool solve(int d) {
    int f1 = getNum();
    if (f1 == 0 ) {
        return true ;
    }
    for (int i = 0 ; i < 4 ; ++ i ) {
        if (status[i][1-d] && check(i, d)) {
            if (i!=0) swap(status[i][0], status[i][1]);
            swap(status[0][0], status[0][1]);
            int x = getNum();
            if (f[x][1-d]) {
                if (i!=0) swap(status[i][0], status[i][1]);
                swap(status[0][0], status[0][1]);
                continue ;
            } else {
                result.push(item[i] + Move[d]);
                f[x][1-d] = true;
                bool f2 = solve(!d);
                if (f2 == false) {
                    result.pop();
                    f[x][1-d] = false ;
                    if (i!=0) swap(status[i][0], status[i][1]);
                    swap(status[0][0], status[0][1]);
                }else{
                    return true;
                }
            }
        }
    }
    return false ; 
}
void print(){
    if(result.empty()){
        return ; 
    }
    string ans = result.top();
    result.pop();
    print();
    cout<<ans<<endl;

}
int main() {
    for(int i = 0 ; i < 4 ; ++ i ) status[i][0]=1;
    f[15][0] = true ;
    if(solve(1)){
        print();
        cout<<"succeed\n";
    }
   
}
// 64 位输出请用 printf("%lld")