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

限制了长度的深度优先搜索

#include<iostream>
#include<vector>

using namespace std;


bool jude(int b[4], int
          k) { //判断当前状态下农夫是否可以带着k(k=1、2、3)移动,或者空手移动（k=4）
    int* a = new int[4];
    for (int i = 0; i < 4; i++)a[i] = b[i];
    if (k != 4) {
        if (a[0] != a[k])return false; //农夫与K(1、2、3)不在同一边
        a[k] = 1 - a[k];
    }
    a[0] = 1 - a[0];
    if (a[1] == a[2] && a[0] != a[2])return false;
    if (a[2] == a[3] && a[0] != a[2])return false;
    free(a);

    return true;
}

void move(int** a, int k) {
    int* b;
    b = *a;
    if (b[0] == 0) {
        b[0] = 1;
        switch (k) {
            case 1:
                cout << "wolf_go" << endl;
                b[k] = 1;
                break;
            case 2:
                cout << "sheep_go" << endl;
                b[k] = 1;
                break;
            case 3:
                cout << "vegetable_go" << endl;
                b[k] = 1;
                break;
            case 4:
                cout << "nothing_go" << endl;
                break;
        }
    } else {
        b[0] = 0;
        switch (k) {
            case 1:
                cout << "wolf_come" << endl;
                b[k] = 0;
                break;
            case 2:
                cout << "sheep_come" << endl;
                b[k] = 0;
                break;
            case 3:
                cout << "vegetable_come" << endl;
                b[k] = 0;
                break;
            case 4:
                cout << "nothing_come" << endl;
                break;
        }
    }
}

bool finish(int a[4]) { //判断是否已经完成任务
    if (a[0] == 0 || a[1] == 0 || a[2] == 0 || a[3] == 0)return false;
    else return true;
}

void findResult(vector<vector<int>>* results, vector<int>* result, int** status,
                int k, int n) {
    if (n == 10)return ; //限制搜索的长度
    //移动
    int* a;
    a = *status;
    a[0] = 1 - a[0];
    if (k != 4)a[k] = 1 - a[k];
    (*result).push_back(k);
    //判断是否找到路径，根据判断结果作出相应的选择
    if (finish(*status)) (*results).push_back(*result);
    else {
        for (int i = 1; i <= 4; i++)
            if (jude(a, i))findResult(results, result, status, i, n + 1);
    }
    //取消移动
    a[0] = 1 - a[0];
    if (k != 4)a[k] = 1 - a[k];
    (*result).pop_back();
}

int main() {
    int* status = new
    int[4]; //status[0]表示农夫，status[1]表示狼，status[2]表示羊，status[3]表示菜
    //0表示其在左边，1表示其在右边 ，假设一开始所有成员都去了左边
    for (int i = 0; i < 4; i++)status[i] = 0;

    vector<vector<int>> results;
    vector<int> result;

    for (int i = 1; i <= 4; i++)
        if (jude(status, i))findResult(&results, &result, &status, i, 1);

    int k = 0;
    for (int i = 0; i < results.size(); i++) {
        if (results[i].size() < results[k].size())k = i;
    }
    for (int i = 0; i < results[k].size(); i++) {
        move(&status, results[k][i]);
    }
    cout << "succeed" << endl;


    return 0;
}