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

深度优先遍历

#include<iostream>
#include<vector>

using namespace std;

void result_output(vector<int> result) {
    int k;
    int status[4] = {0};
    vector<int>::iterator it;
    for (it = result.begin(); it != result.end(); it++) {
        k = *it;
        switch (k) {
            case 1:
                if (status[1] == 0)cout << "wolf_go" << endl;
                else cout << "wolf_come" << endl;
                break;
            case 2:
                if (status[2] == 0)cout << "sheep_go" << endl;
                else cout << "sheep_come" << endl;
                break;
            case 3:
                if (status[3] == 0)cout << "vegetable_go" << endl;
                else cout << "vegetable_come" << endl;
                break;
            case 4:
                if (status[0] == 0)cout << "nothing_go" << endl;
                else cout << "nothing_come" << endl;
                break;

        }
        if (k != 4)status[k] = 1 - status[k];
        status[0] = 1 - status[0];
    }
    cout << "succeed";
}

bool move_jude(int status[4], int k) { //判断走某一步是否合法
    int flag = 1;
    if (k != 4) { //农夫没有空走
        if (status[0] != status[k])return false; //农夫和k不在同一边
        status[k] = 1 - status[k];
    }
    status[0] = 1 - status[0];
    if (status[0] != status[2] && (status[1] == status[2] ||
                                   status[2] == status[3]))flag = 0;
    if (k != 4)status[k] = 1 - status[k];
    status[0] = 1 - status[0];
    if (flag == 0)return false;
    else return true;
}

bool result_jude(int status[4]) {
    if (status[0] == 1 && status[1] == 1 && status[2] == 1 &&
            status[3] == 1)return true;
    else return false;
}

void find_results(vector<vector<int>>* results, vector<int>* result,
                  int* status, int k, int n) {
    if (n == 10)return;
    //移动
    if (k != 4)status[k] = 1 - status[k];
    status[0] = 1 - status[0];
    result->push_back(k);
    //判断是否搜索到结果
    if (result_jude(status))results->push_back(*result);
    //进一步搜索
    else
        for (int i = 1; i <= 4; i++)
            if (move_jude(status, i))find_results(results, result, status, i, n + 1);
    //移出
    if (k != 4)status[k] = 1 - status[k];
    status[0] = 1 - status[0];
    result->pop_back();
}

int main() {
    int status[4] = {0}; //数组各个位置变量的意义：0农夫 1狼 2羊 3菜
    //每个位置的值的含义：0代表此岸 1代表对岸
    vector<vector<int>> results;
    vector<int> result;

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

    vector<int> min = results[0];
    for (int i = 0; i < results.size(); i++) {
        if (results[i].size() < min.size())min = results[i];
    }

    result_output(min);

    return 0;
}