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

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

class FSM {
  private:
    vector<bool>* status;
    vector<int>* action;
  public:
    FSM() {
        status = new vector<bool>(4, false);
        action = new vector<int>();
    }
    FSM(FSM& f) {
        status = new vector<bool>(*f.status);
        action = new vector<int>(*f.action);
    }
    bool if_finish() {
        for (auto iter = status->begin(); iter != status->end(); ++iter) {
            if (*iter == false) return false;
        }
        return true;
    }
    bool if_legel() {
        if ((!((*status)[1] ^ (*status)[2]) || !((*status)[1] ^ (*status)[3])) &&
                ((*status)[0] ^ (*status)[1])) 
                return false;
        else 
            return true;
    }
    const char* message(int idx) {
        switch (idx) {
            case 0:
                return "nothing_go";
            case 1:
                return "sheep_go";
            case 2:
                return "vegetable_go";
            case 3:
                return "wolf_go";
            case 4:
                return "nothing_come";
            case 5:
                return "sheep_come";
            case 6:
                return "vegetable_come";
            case 7:
                return "wolf_come";
            default:
                return "error";
        }
    }
    void print() {
        for (auto iter = action->begin(); iter != action->end(); ++iter) {
            cout << message(*iter) << endl;
        }
        cout << "succeed" << endl;
    }
    FSM* transition(int mode) {
        int bias = (*status)[0] ? 4 : 0;
        FSM* f = new FSM(*this);
        f->action->push_back(mode + bias);
        if (mode) {
            if ((*f->status)[0] ^ (*f->status)[mode]) {
                return nullptr;
            }
            (*f->status)[mode] = !(*f->status)[mode];
        } 
        (*f->status)[0] = !(*f->status)[0];
        if (f->if_legel()) 
            return f;
        return nullptr;
    }
};

int main() {
    queue<FSM *> fsm_queue;
    auto initial = new FSM();
    fsm_queue.push(initial);
    while (!fsm_queue.empty()) {
        auto s = fsm_queue.front();
        if (s->if_finish()) {
            s->print();
            break;
        }
        for (int i = 0; i < 4; ++i) {
            auto tmp = s->transition(i);
            if (tmp) 
                fsm_queue.push(tmp);
        }
        fsm_queue.pop();
        delete s;
    }
    return 0;
}
// 64 位输出请用 printf("%lld")

广度优先搜索，用4个布尔值描述每个状态，每种状态都有四种模式的转移。（提交代码时本来想用delete释放内存，但是用delete会报错）