首页 > 试题广场 >

农夫、羊、菜和狼的故事

[编程题]农夫、羊、菜和狼的故事
  • 热度指数:4080 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
有一个农夫带一只羊、一筐菜和一只狼过河。如果没有农夫看管,则狼要吃羊,羊要吃菜。但是船很小,只够农夫带一样东西过河。问农夫该如何解此难题?

输入描述:
题目没有任何输入。


输出描述:
题目可能有多种解决方法,请输出步骤最少的任意一种解决方法,
按顺序输出农夫想把羊、菜、狼全部运过河需要哪几个步骤。
如果需要将羊带过河去则输出一行“sheep_go”。
如果需要将羊带回来则输出一行“sheep_come”。
如果需要将菜带过河去则输出一行“vegetable_go”。
如果需要将菜带回来则输出一行“vegetable_come”。
如果需要将狼带过河去则输出一行“wolf_go”。
如果需要将狼带回来则输出一行“wolf_come”。
如果需要空手返回则输出一行“nothing_come”。
如果需要空手过河则输出一行“nothing_go”。
输出任意一种可行的最简方案后,请在最后输出一行“succeed”。
示例1

输入

输出

按题目要求进行输出即可。
//羊go 无come 菜go 羊come 狼go 无come 羊go,前提条件羊必须自己在一边
#include<stdio.h>
int main()
{
    printf("sheep_go\n");
    printf("nothing_come\n");
    printf("vegetable_go\n");
    printf("sheep_come\n");
    printf("wolf_go\n");
    printf("nothing_come\n");
    printf("sheep_go\n");
    printf("succeed\n");
}

发表于 2020-03-30 21:49:07 回复(0)
//明显要用到回溯法
#include<stdio.h>
#include<string.h>

typedef struct record{
    int type; //sheep|vegetable|wolf|nothing
    int dir; //come|go
}Rec;

char state[5]; //代表🐏🐺菜人的状态
Rec list[20];
int count;

int Judge(int x,int direct){//其实可以用map来做,可以很方便的去重
    if(strcmp(state,"0111")==0&&x!=3)  //防止无限循环
        return 0;
    if(count!=0&&x==list[count-1].type)//防止无限循环,例如第一次把羊带过去第二次又带回来
        return 0;
    if(x==3)//nothing
    {
        if(state[0]==state[1]||state[0]==state[2])
            return 0;
        return 1;
    }
    if(state[x]!=state[3])//想要带的和农夫根本不在一边
        return 0;
    else {
        char tmp[5];
        strcpy(tmp,state);
        tmp[x]='1'-tmp[x]+'0';
        tmp[3]='1'-tmp[3]+'0';
        if((tmp[0]==tmp[1]||tmp[0]==tmp[2])&&tmp[0]!=tmp[3])
            return 0;
        return 1;
    }
}

void dfs(char * state,int direct){
     if(strcmp(state,"1111")==0)
     {
         for(int i=0;i<count;i++){
             switch(list[i].type){
                 case 0:printf("sheep_");break;
                 case 1:printf("wolf_");break;
                 case 2:printf("vegetable_");break;
                 case 3:printf("nothing_");break;
             }
             switch(list[i].dir){
                 case 0:printf("go\n");break;
                 case 1:printf("come\n");break;
             }
         }
         printf("succeed\n");
         return;
     }
     for(int i=3;i>=0;i--){//代表四个type,每次都从什么都不带开始遍历。
        if(Judge(i,direct)){
            char tmp = state[i];
            list[count].type=i;//记录该操作
            list[count].dir=direct;
            count++;
            state[i]=state[3]=1-direct+'0';//更改状态
            dfs(state,1-direct);
            state[i]=state[3]=tmp;//回溯
            count--;
        }
    }
}

int main(){
    strcpy(state,"0000");
    count = 0;
    dfs(state,0);
}

编辑于 2020-03-18 21:17:53 回复(1)
#include<stdio.h>
int main(void)
{
    printf("sheep_go\r\n");
    printf("nothing_come\r\n");
    printf("vegetable_go\r\n");
    printf("sheep_come\r\n");
    printf("wolf_go\r\n");
    printf("nothing_come\r\n");
    printf("sheep_go\r\n");
    printf("succeed\r\n");
}
发表于 2019-04-23 20:52:27 回复(0)
#include <stdio.h>
#include <stdlib.h>
//农夫过河问题,用1111的二进制分别代表河的一岸的农夫、狼、羊、菜,假如农夫带狼过河则1111变为0011
//总共有16种状态,每次过河的操作(8种操作)都会变成另外一个状态,直到得到0000,
//可以得到一个状态树,保存满足条件的路径
//不满足题目要求的状态有0111,0110,0011,1000,1001,1100
//建立一个当前搜索队列,保存遍历的状态,出现重复的状态则不进行这次变化(避免死循环),若队尾出现0,退出搜索
#define nothing_go -8
#define nothing_come 8
#define wolf_go -12
#define wolf_come 12
#define vegetable_go -9
#define vegetable_come 9
#define sheep_go -10
#define sheep_come 10
int Move[8] = {-12, -10, -9, -8, 8, 9, 10, 12};
typedef struct Results{
    int r[100];
    int length;
}Results;
Results Result[10];
int re_num=0;
int queue[100],length=0;  //队列长度
int judge(int b, int m){//判断此次变化是否满足过河要求
    int i, a = b + m;
    if(m>0&&(m-8)&b>0)//如果是回来,那么你带的物品一定是这边没有的
        //(m-8)&b==0表示带来的物品这边没有,防止羊被分解成菜带回来了
        return 0;
    if(m<0&&(abs(m)-8)&b==0)//带过去的物品一定要存在
        return 0;

    //判断过河后的状态是否满足条件或者出现过
    if(a>15||a<0)
        return 0;
    if(a==12||a==9||a==8||a==7||a==6||a==3)
        return 0;
    for(i=0;i<length;i++)
        if(a==queue[i])
            return 0;
    return 1;
}
//8种变化分别为
int Rivercross(int a){//生成状态树
    int i;
    queue[length]=a;
    if(a==0){//过河成功,保存队列信息
        for(i=0;i<length;i++){
            Result[re_num].r[i]=queue[i];
        }
        Result[re_num].length=length+1;
        re_num++;
        return 1;
    }
    for(i = 0; i < 8; ++i) {
        ++length;
        if(judge(a, Move[i]))
            Rivercross(a + Move[i]);
        --length;
    }
}
void myprint(int index){//格式化输出
    int i;
    for(i=0;i<Result[index].length-1;i++){
        switch(Result[index].r[i+1]-Result[index].r[i]){
            case -8:printf("nothing_go\n");break;
            case 8:printf("nothing_come\n");break;
            case -12:printf("wolf_go\n");break;
            case 12:printf("wolf_come\n");break;
            case -9:printf("vegetable_go\n");break;
            case 9:printf("vegetable_come\n");break;
            case -10:printf("sheep_go\n");break;
            case 10:printf("sheep_come\n");break;
        }
    }
}
int main()
{
    int i,min_index=0;
    Rivercross(15);
    for(i=1;i<re_num;i++)//寻找最短路径序号
        if(Result[i].length<Result[min_index].length)
            min_index=i;
    for(i=0;i<re_num;i++){//等于最短路径长度的结果输出
        if(Result[i].length == Result[min_index].length){
            myprint(i);
            printf("succeed\n\n");
        }
    }
}


编辑于 2020-03-13 12:59:24 回复(6)
#include<stdio.h>
int main()
{
    printf("sheep_go\n");
    printf("nothing_come\n"); 
    printf("vegetable_go\n");
    printf("sheep_come\n"); 
    printf("wolf_go\n");
    printf("nothing_come\n"); 
    printf("sheep_go\n");
    printf("succeed");
}
想了半天发现这道题是单例检验,直接输出就完事了

发表于 2021-05-01 16:40:34 回复(0)
//最近刚学的算法,这属于用的回溯吗?
//感觉题目出的不严谨,因为最后输出的方案应该是有两个,第三步应该可以菜过河,也可以狼过河
//所以我的输出是两个,然而题目的答案只输出了一个😓😓😓。

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

typedef struct Record{
    int passage;//0 vegetables ; 1 sheep ; 2 wolf ;3 nothing
    int ifgo;   //1 go ; 0 come 
    Record(int a,int b):passage(a),ifgo(b){}
}Record;

vector<vector<Record> > result;  //存储可行的乘船经历
vector<Record> rec;             //记录当前状态

int goline[3]={1,1,1}; //等待过河的队伍的存在状态,1代表在,0代表不在(即在对面),3代表在渡船,下标0代表蔬菜,1代表羊,2代表狼

void goRiver(int lastPass);
void comeRiver(int lastPass);

bool ifFeasible(){
    if(goline[2]==goline[1]||goline[1]==goline[0]) return false;
    return true;
}

bool ifEnd(){
    for(int i=0;i<3;i++){
        if(goline[i]!=0) return false;
    }
    return true;
}

void goRiver(int lastPass){

    for(int i=0;i<3;i++){
        if(goline[i]&&goline[i]!=lastPass){
            goline[i]=3;
            if(ifFeasible()){
                goline[i]=0;
                Record q(i,1);
                rec.push_back(q);
                comeRiver(i);

                goline[i]=1;
                rec.pop_back();
            }else{
                goline[i]=1;
            }
        }
    }
    return;
}

void comeRiver(int lastPass){

     if(ifEnd()){
        result.push_back(rec);
        return;
    }

    if(ifFeasible()){
        Record q(3,0);
        rec.push_back(q);
        lastPass=3;
        goRiver(lastPass);
    }

    for(int i=0;i<3;i++){
        if(goline[i]==0&&goline[i]!=lastPass){
            goline[i]=3;
            if(ifFeasible()){
                goline[i]=1;
                Record q(i,0);
                rec.push_back(q);
                goRiver(i);

                goline[i]=0;
                rec.pop_back();
            }else{
                goline[i]=0;
            }
        }
    }
    return;
}

int minRecord(){
    int minnum=0;
    for(int i=0;i<result.size();i++){
        if(result[i].size()<minnum) minnum=result[i].size();
    }

    return minnum;
}

void printProcess(int n){

    for(int i=0;i<result[n].size();i++){
        string a,b;

        switch(result[n].at(i).passage){
            case 0:
                a="vegetable_";
                break;
            case 1:
                a="sheep_";
                break;
            case 2:
                a="wolf_";
                break;
            case 3:
                a="nothing_";
                break;
        }
        switch(result[n].at(i).ifgo){
        case 0:
            b="come";
            break;
        case 1:
            b="go";
            break;
        }

        cout<<a<<b<<endl;

    }
}
int main(){

    goRiver(-1);
    int minnum=minRecord();

    for(int i=0;i<result.size();i++){
        if(result[i].si***num){
            printProcess(i);
            cout<<"succeed"<<endl;
        }
    }
}

发表于 2019-02-26 09:11:06 回复(1)
每次都让羊待在一边就行
发表于 2019-02-22 23:18:43 回复(0)
//1.农夫带🐏去
//2.农夫自己回
//3.农夫带菜去
//4.农夫带🐏回
//5.农夫带🐺去
//6.农夫空手回
//7.农夫带🐏去
#include<bits/stdc++.h>
using namespace std;
int main(){
    printf("sheep_go\n");
    printf("nothing_come\n");
    printf("vegetable_go\n");
    printf("sheep_come\n");
    printf("wolf_go\n");
    printf("nothing_come\n");
    printf("sheep_go\n");
    printf("succeed\n");
    return 0;
}
发表于 2020-01-20 15:39:11 回复(3)
#include<iostream>
#include <string>
#include <type_traits>
#include <vector>
#include <algorithm>
using namespace std;
bool danger(int& f, int& s, int& v, int& w);
bool visited(vector<string>& state, string s);
string build(int f, int s, int v, int w);
bool test(int& f, int& s, int& v, int& w, vector<string>& state);
bool cheak(int f, int s, int v, int w, vector<string>& state);

bool danger(int& f, int& s, int& v,
            int& w) {  //检测是否处于危险状态。
    if ((s == v && f != s) || (w == s && f != w)) return true;
    else return false;
}

bool visited(vector<string>& state,
             string s) {  //检测该状态是否已经访问过。
    if (find(state.begin(), state.end(), s) != state.end()) {
        return true;
    } //访问过该状态则返回真
    else {
        state.push_back(
            s); //未访问过时则将此状态记录,并访问该状态。
        return false;
    }
}

string build(int f, int s, int v,
             int w) {  //描述当前状态,生成状态字符串。
    string temp;
    temp.append(to_string(f));
    temp.append(to_string(s));
    temp.append(to_string(v));
    temp.append(to_string(w));
    return temp;
}

bool cheak(int f, int s, int v, int w,
           vector<string>& state) {  //根据当前环境与状态队列来判断当前状态是否访问过。
    string str = build(f, s, v, w);
    // for (auto it = state.begin(); it != state.end(); it++) cout << *it << ' ';
    // cout << endl;
    return visited(state, str);
}

bool test(int& f, int& s, int& v, int& w, vector<string>& state) {
    if (f & s & v & w) {
        cout << "succeed" <<
             endl;  //找到解时输出,并返回真值以结束查找。
        return true;
    } else {
        if (f == 0) {
            f = 1;
            if (danger(f, s, v, w) || cheak(f, s, v, w, state)) {
                f = 0;  //新状态危险或已访问时,进行回溯。
            } else {
                cout << "nothing_go" << endl;
                if (test(f, s, v, w, state)) return
                        true; //若找到解,则会逐层返回真值以退出递归。
                f = 0;  //上一条路径无法找到解时,同样进行回溯。
            }
            if (s == f) {
                f = 1;
                s = 1;
                if (danger(f, s, v, w) || cheak(f, s, v, w, state)) {
                    f = 0;
                    s = 0;
                } else {
                    cout << "sheep_go" << endl;
                    if (test(f, s, v, w, state)) return true;
                    f = 0;
                    s = 0;
                }
            }
            if (v == f) {
                f = 1;
                v = 1;
                if (danger(f, s, v, w) || cheak(f, s, v, w, state)) {
                    f = 0;
                    v = 0;
                } else {
                    cout << "vegetable_go" << endl;
                    if (test(f, s, v, w, state)) return true;
                    f = 0;
                    v = 0;
                }
            }
            if (w == f) {
                f = 1;
                w = 1;
                if (danger(f, s, v, w) || cheak(f, s, v, w, state)) {
                    f = 0;
                    w = 0;
                } else {
                    cout << "wolf_go" << endl;
                    if (test(f, s, v, w, state)) return true;
                    f = 0;
                    w = 0;
                }
            }
        } else {
            f = 0;
            if (danger(f, s, v, w) || cheak(f, s, v, w, state)) {
                f = 1;
            } else {
                cout << "nothing_come" << endl;
                if (test(f, s, v, w, state)) return true;
                f = 1;
            }
            if (s == f) {
                f = 0;
                s = 0;
                if (danger(f, s, v, w) || cheak(f, s, v, w, state)) {
                    f = 1;
                    s = 1;
                } else {
                    cout << "sheep_come" << endl;
                    if (test(f, s, v, w, state)) return true;
                    f = 1;
                    s = 1;
                }
            }
            if (v == f) {
                f = 0;
                v = 0;
                if (danger(f, s, v, w) || cheak(f, s, v, w, state)) {
                    f = 1;
                    v = 1;
                } else {
                    cout << "vegetable_come" << endl;
                    if (test(f, s, v, w, state)) return true;
                    f = 1;
                    v = 1;
                }
            }
            if (w == f) {
                f = 0;
                w = 0;
                if (danger(f, s, v, w) || cheak(f, s, v, w, state)) {
                    f = 1;
                    w = 1;
                } else {
                    cout << "wolf_come" << endl;
                    if (test(f, s, v, w, state)) return true;
                    f = 1;
                    w = 1;
                }
            }
        }
        return false;  //未找到解时返回假值以进行回溯。
    }
}

int main() {
    int farm = 0, sheep = 0, veg = 0, wolf = 0;
    vector<string> state;
    string s;
    s = build(farm, sheep, veg, wolf);  // 初始化状态队列。
    state.push_back(s);
    test(farm, sheep, veg, wolf, state);
    return 0;
}

发表于 2023-03-22 02:15:34 回复(0)
#include <iostream>
#include <stdio.h>
using namespace std;
/*
用8位bit来表示两岸的状态,假设是从右岸到左岸, 右岸和左岸分别有四个状态,即 菜,羊,狼,农夫, 1表示在此岸,0表示不在此岸
初始时,为 0b0000 1111, 表示 菜,羊,狼,农夫全部在右岸。 有两岸,4种move,总共8种,如0b00000011,表示狼和农夫一起从右岸走, 0b00110000,表示狼和农夫一起从左岸走。
1.判断是否全到左岸,是则退出递归并输出相应的move。否,从四种move中选择一种,进入2
2.判断此岸是否有条件进行move,如此岸有狼才能wolf_go或wolf_come。若是,进入3,否,返回1 
3.判断move与上次move是否对应,如 上次nothing_go,此次不能再次nothing_come。 若是,返回1,若否,进入4
4.渡河,两岸的状态改变,判断 离开的那一岸,是否会出现狼吃羊,羊吃菜的现象,若是,返回1,若否,进入5
5.更新两岸状态,回到1继续判断
中间遇到一个bug,也就是move_flag的顺序改变,第一个不是nothing_come和nothing_go,会陷入无限循环:
sheep_go, nothing_come, wolf_go, sheep_come, vegetable_go。 此时羊在右岸,农夫,狼和菜在左岸。
如果下一步选择 wolf_come, 那么就会出现死循环,而nothing_come则就能正确得出解。
改变move_flag内的顺序,就会出现bug
u8 move_flag[2][4] = {   {WOLF_GO, SHEEP_GO, VEGETABLE_GO, NOTHING_GO},
                    {WOLF_COME, SHEEP_COME, VEGETABLE_COME, NOTHING_COME}};
将nothing_go,nothing_come放在第一个位置,隐含左岸优先级比右岸高,否则会出现两岸是等同地位,跳不出循环
*/

#define WOLF_EAT_SHEEP_RIGHT 0x06 // 农夫离开右岸,出现狼吃羊
#define WOLF_EAT_SHEEP_LEFT 0x60  // 左岸,狼吃羊
#define SHEEP_EAT_VEG_RIGHT 0x0c  // 右岸,羊吃菜
#define SHEEP_EAT_VEG_LEFT 0xc0   // 左岸,羊吃菜
#define RIGHT 0
#define LEFT 1
#define MAX_SIZE 300
#define NOTHING_GO              0b00000001
#define NOTHING_COME            0b00010000
#define WOLF_GO                 0b00000011
#define WOLF_COME               0b00110000
#define SHEEP_GO                0b00000101
#define SHEEP_COME              0b01010000
#define VEGETABLE_GO            0b00001001
#define VEGETABLE_COME          0b10010000

typedef unsigned char u8;

string a[MAX_SIZE];

u8 move_flag[2][4] = {   {NOTHING_GO, WOLF_GO, SHEEP_GO, VEGETABLE_GO},
                    {NOTHING_COME, WOLF_COME, SHEEP_COME, VEGETABLE_COME}};

void init() {
    a[NOTHING_GO]   = "nothing_go";
    a[WOLF_GO]      = "wolf_go";
    a[SHEEP_GO]     = "sheep_go";
    a[VEGETABLE_GO] = "vegetable_go";
    a[NOTHING_COME] = "nothing_come";
    a[WOLF_COME]    = "wolf_come";
    a[SHEEP_COME]   = "sheep_come";
    a[VEGETABLE_COME] = "vegetable_come";
}

void cross_river(u8 river_flag, bool &zflag, u8 last_move) {
    if ( river_flag == 0b11110000) { // 都到左岸,退出递归
        zflag = true;
        return ;
    }
    int this_side = (river_flag & 0x01) == 0x01 ? RIGHT : LEFT;
    int that_side = (river_flag & 0x01) == 0x01 ? LEFT : RIGHT;
   
    for (int i = 0; i < 4; i++) {
        if ((move_flag[this_side][i] & river_flag) != move_flag[this_side][i] ) { // 判断this_side有对应的事物才能带到对面去,也就能执行相应的move
            continue;
        }
        if (last_move == move_flag[that_side][i]) { // 上一次和此次的move应该不一致,否则此次move是无意义的
            continue;
        }

        u8 rf_temp = river_flag - move_flag[this_side][i] | move_flag[that_side][i]; // 渡河,到达了对岸,此时两岸的状态

        // 离开了右岸,判断右岸是否出现了狼吃羊,或羊吃菜的现象
        if (this_side == RIGHT &&  ((rf_temp & WOLF_EAT_SHEEP_RIGHT) == WOLF_EAT_SHEEP_RIGHT  || (rf_temp & SHEEP_EAT_VEG_RIGHT) == SHEEP_EAT_VEG_RIGHT)) {
            continue;
        }
        // 离开了左岸,判断左岸是否出现了狼吃羊,或羊吃菜的现象
        if (this_side == LEFT && ((rf_temp & WOLF_EAT_SHEEP_LEFT) == WOLF_EAT_SHEEP_LEFT || (rf_temp & SHEEP_EAT_VEG_LEFT) == SHEEP_EAT_VEG_LEFT) ) {
            continue;
        }
        // 上述条件都通过,此次move有意义,进入下一次抉择
        cross_river(rf_temp, zflag, move_flag[this_side][i]);
        if (zflag) {
            cout << a[move_flag[this_side][i]] << endl;
            return;
        } 
    }
    
}


int main() {
    u8 river_flag = 0x0f;  // 0b 0000 1111, 低四位是右边的河岸,从右到左,1表示 农夫,狼,羊,菜
    bool zflag = false;
    init();
    cross_river(river_flag, zflag, 0x00);
    if (zflag) {
        cout << "succeed" << endl;
    }
    return 0;
}
// 64 位输出请用 printf("%lld")

发表于 2023-03-03 09:16:55 回复(0)
广度优先搜索,在求最终的路径时感觉绕弯有点多,求指点😊
#include <stdio.h>
#include <queue>
 using namespace std;
 queue<int> S;
 int visit[20];//用来保存当前状态的前一状态
 int a[4]={8,12,10,9};//用来表示4种状态转换操作
 bool judge(int x)
 {//用来判断是否为合法状态
     if(x>=5&&x<=10)
     return false;
     else if(x>15 || x<0)
     return false;
     else if(visit[x]!=-1)
     return false;
     else
     return true;
 }
 void BFS()
 {
     int current=S.front();
     S.pop();
     for(int i=0;i<4;i++ )
     {
         int next=a[i]^current;
         if(judge(next))
         {    
         S.push(next);
         visit[next]=current;
         if(next == 15)
         return;
         }
     }
     BFS();
 }
 void myprint(int a1,int a2)
 {
     switch(a2-a1)
     {    
         case -8: printf("nothing_come\n");break;
         case -12: printf("sheep_come\n");break;
         case -10: printf("vegetable_come\n");break;
         case -9: printf("wolf_come\n");break;
         case 8: printf("nothing_go\n");break;
         case 12: printf("sheep_go\n");break;
         case 10: printf("vegetable_go\n");break;
         case 9: printf("wolf_go\n");break;
     }
 }
 int main()
 {
     int state =0;
     for(int i=0;i<16;i++)
     visit[i]=-1;
     S.push(state);
     visit[state]=-2;
        BFS();
     int x=15;
     int a[20];//根据visit数组来获得路径顺序,即状态序列
     int idx=0;
     while(x!=-2)
     {
         a[idx++]=x;
         x=visit[x];
     }
     for(int i=idx-1;i>0;i--)
      {//根据a数组即状态序列的变换打印状态转换过程
            myprint(a[i],a[i-1]);
         }
     printf("succeed\n");
     return 0;
 }
编辑于 2019-07-28 15:27:57 回复(0)
羊过去空手回来此时既可以让狼过去也可以让菜过去
之后带羊回 把不是羊的那个带过去 空手回 最后带羊过去
应该有两种方案才对啊
发表于 2019-03-17 01:19:58 回复(0)
print("sheep_go")
print("nothing_come")
print("wolf_go")
print("sheep_come")
print("vegetable_go")
print("nothing_come")
print("sheep_go")
print("succeed")

发表于 2024-03-14 21:06:45 回复(0)
#include <iostream>
using namespace std;

int main() {
    puts("sheep_go");
    puts("nothing_come");
    puts("wolf_go");
    puts("sheep_come");
    puts("vegetable_go");
    puts("nothing_come");
    puts("sheep_go");
    puts("succeed");
    return 0;
}
只会暴力~
编辑于 2024-03-14 20:51:24 回复(0)
宽度优先遍历
#include <iostream>
#include <vector>
#include <queue>
#include <map>
using namespace std;

bool is_visited[2][2][2][2] = { false };

struct State{
    int person;
    int wolf;
    int sheep;
    int vegetable;
    int path;    //记录之前的操作序列,每一位代表一个操作
    State(int p,int w,int s,int v, int way):person(p),wolf(w),sheep(s),vegetable(v),path(way){}
};

//(人,狼,羊,菜)四元组,0表示在此岸,1表示在对岸
bool is_valid(int p, int w, int s, int v){
    if(w == s && p != w)
        return false;
    if(s == v && p != s)
        return false;
    if(p < 0 || w < 0 || s < 0 || v < 0)
        return false;
    if(p > 1 || w > 1 || s > 1 || v > 1)
        return false;
    if(p == 0 && w == 0 && s == 0 && v == 0)
        return false;

    return !is_visited[p][w][s][v];
}

bool operation(int op, State &s){
    int np = s.person, nw = s.wolf, ns = s.sheep, nv = s.vegetable;
    switch (op){
        case 1:
            np++;
            ns++;
            break;
        case 2:
            np--;
            ns--;
            break;
        case 3:
            np++;
            nv++;
            break;
        case 4:
            np--;
            nv--;
            break;
        case 5:
            np++;
            nw++;
            break;
        case 6:
            np--;
            nw--;
            break;
        case 7:
            np++;
            break;
        case 8:
            np--;
            break;
    }

    if(is_valid(np, nw, ns, nv)){
        s.person = np, s.wolf = nw, s.sheep = ns, s.vegetable = nv;
        s.path = s.path * 10 + op;
        return true;
    }
    else
        return false;
}

void display(int path){ //输出转移方法
    string str = to_string(path);
    while(str.size() != 0){
        switch (str[0] - '0'){
        case 1:
            cout<<"sheep_go"<<endl;
            break;
        case 2:
            cout<<"sheep_come"<<endl;
            break;
        case 3:
            cout<<"vegetable_go"<<endl;
            break;
        case 4:
            cout<<"vegetable_come"<<endl;
            break;
        case 5:
            cout<<"wolf_go"<<endl;
            break;
        case 6:
            cout<<"wolf_come"<<endl;
            break;
        case 7:
            cout<<"nothing_go"<<endl;
            break;
        case 8:
            cout<<"nothing_come"<<endl;
            break;
        }
        str.erase(str.begin());
    }
}

void bfs(State s){
    queue<State> myqueue;
    myqueue.push(s);
    while(!myqueue.empty()){
        State temp = myqueue.front();
        myqueue.pop();

        if(temp.person == 1 && temp.wolf == 1 && temp.sheep == 1 && temp.vegetable == 1){
            display(temp.path);
            cout<<"succeed"<<endl;
            return ;
        }

        for(int i = 1; i <= 8; i++){
            bool flag = operation(i, temp);
            if(flag){
                is_visited[temp.person][temp.wolf][temp.sheep][temp.vegetable] = true;
                myqueue.push(temp);
            }
        }
    }
}

int main() {
    State start(0, 0, 0, 0, 0);
    bfs(start);
}

发表于 2024-03-06 17:09:40 回复(0)
最少的步骤,故采用 BFS
(1)状态空间:(标记数组 flags, 当前步骤 step, 过河过程 process)
(2)状态转移:flags 中和农夫在一起的可以随农夫过河(或者什么都不带),step + 1, process += i(0, 1, 2, 3)
(3)起始状态:({X, 0, 0, 0}, 0, "")
(4)目标状态:({X, 1, 1, 1, Odd, "xxxxxxx"}

搜索树:
                    ({0,0,0}, 0, "")
                              /
                 ({0,1,0}, 1, "1")
                           /  \
({0,1,0}, 2, "10")      ({0,0,0}, 2, "11")  ......
#include <iostream>
#include <string>
#include <queue>

using namespace std;

string map[4] = {"nothing", "vegetable", "sheep", "wolf"};

struct Status {
    bool flags[4];  // 下标 1, 2, 3 分别表示蔬菜,羊,狼,下标 0 冗余;false 表示在河这岸,true 表示过河对岸
    int step;       // 表当前第几步,为偶数时农夫在河这岸,为奇数时农夫过河对岸
    string process; // 过河步骤过程
    Status(bool f[3], int s, string p) {
        flags[0] = false;
        for (int i = 1; i <= 3; i++) {
            flags[i] = f[i - 1];
        }
        step = s;
        process = p;
    }
};

bool Valid(const Status& s) {
    bool f = s.step % 2 == 0;   // 偶数时农夫在河这岸,就检查河对岸;反之亦然
    // if (s.flags[1] == f && s.flags[2] == f) {   // 蔬菜和羊在一起
    //     return false;
    // }
    // if (s.flags[2] == f && s.flags[3] == f) {   // 羊和狼在一起
    //     return false;
    // }
    // return true;
    return !(s.flags[1] == f && s.flags[2] == f || s.flags[2] == f && s.flags[3] == f);
}

bool Succeed(const Status& s) {
    return s.flags[1] && s.flags[2] && s.flags[3];  // 蔬菜,羊和狼都到达河对岸
}

string BFS() {
    queue<Status> q;
    bool initFlags[3] = {false, false, false};
    q.push(Status(initFlags, 0, ""));   // 压入初始状态
    while (!q.empty()) {
        Status cur = q.front();
        q.pop();
        if (Succeed(cur)) {         // 找到了目标状态
            return cur.process;
        }

        for (int i = 0; i <= 3; i++) {
            Status next = cur;      // 每轮循环都创建一个新的 next,避免各个 next 数据互相影响
            next.step ++;
            next.process += (i + '0');      // 当前步骤带什么过河,0 表示什么都不带

            bool flag = next.step % 2 == 1;
            if (i != 0 && !next.flags[i] == flag) { // 如果当前步骤农夫要过河对岸,则只能带目前在河这岸的;反之亦然
                next.flags[i] = flag;
            }

            if (Valid(next)) {
                q.push(next);
            }
        }
    }
}

void PrintProcess(string process) {
    for (int i = 0; i < process.size(); i++) {
        if (i % 2) {
            cout << map[process[i] - '0'] << "_come" << endl;
        } else {
            cout << map[process[i] - '0'] << "_go" << endl;
        }
    }
    cout << "succeed" << endl;
}

int main() {
    string process = BFS();
    PrintProcess(process);
    return 0;
}


发表于 2022-05-01 22:55:07 回复(0)
//不会回溯。。。自己写了个逻辑调好半天。。。
#include <iostream>
#include <string.h>
using namespace std;
void goahead();
void print(int a[],int n);
const int maxin=10;
int arr[2][3];
int step[maxin];
int final_step[maxin];
int len=0,num=0;
int cnt=-1;

bool judge_OK(int a[])
{
    if(a[0]&&a[1])
        return false;
    else if(a[1]&&a[2])
        return false;
    else return true;
}
void goback()
{
    if(arr[1][0]&&arr[1][1]&&arr[1][2])
    {
        if(!num||num>len)
        {
            num=len;
            for(int i=0;i<num;i++)
                final_step[i]=step[i];
        }
        return;
    }
    int pre=cnt;
    for(int i=0;i<4;i++)
    {
        if(arr[1][0]&&arr[1][2]) i=3;
        if(i!=cnt&&arr[1][i]&&i!=3)
        {
            arr[1][i]=0;
            if(!judge_OK(arr[1])) arr[1][i]=1;
            else
            {
                arr[0][i]=1;
                cnt=i;
                step[len++]=i;
                goahead();
                len--;
                cnt=pre;
                arr[0][i]=0;
                arr[1][i]=1;
            }
        }
        else if(i==3)
        {
            if(!judge_OK(arr[1])) break;
            else{
                cnt=-1;
                step[len++]=i;
                goahead();
                len--;
                cnt=pre;
            }
        }
    }
}
void goahead()
{
    for(int i=0;i<4;i++)
    {
        int pre=cnt;
        if(i!=cnt&&i!=3&&arr[0][i])
        {
            arr[0][i]=0;
            if(!judge_OK(arr[0])) arr[0][i]=1;
            else
            {
                arr[1][i]=1;
                cnt=i;
                step[len++]=i;
                goback();
                len--;
                cnt=pre;
                arr[1][i]=0;
                arr[0][i]=1;
            }
        }
        else if(i==3&&!arr[0][0]&&!arr[0][1]&&!arr[0][2])
        {
            if(!judge_OK(arr[0])) break;
            else{
                cnt=-1;
                step[len++]=i;
                goback();
                len--;
                cnt=pre;
            }
        }
    }
}
void print(int a[],int n)
{
    for(int i=0;i<n;i++)
    {
        if(i%2)
        {
            switch(a[i])
            {
                case 0:cout<<"wolf_come"<<endl;
                    break;
                case 1:cout<<"sheep_come"<<endl;
                    break;
                case 2:cout<<"vegetable_come"<<endl;
                    break;
                case 3:cout<<"nothing_come"<<endl;
                    break;
                default:break;
            }
        }
        else
        {
            switch(a[i])
            {
                case 0:cout<<"wolf_go"<<endl;
                    break;
                case 1:cout<<"sheep_go"<<endl;
                    break;
                case 2:cout<<"vegetable_go"<<endl;
                    break;
                case 3:cout<<"nothing_go"<<endl;
                    break;
                default:break;
            }
        }
    }
    cout<<"succeed"<<endl;
}
int main()
{
    for(int i=0;i<3;i++)
    {
        arr[0][i]=1; //0表示狼,1表示羊,2表示菜,3表示空手;
        arr[1][i]=0;
    }
    goahead();
    print(final_step,num);
}


发表于 2022-02-19 19:19:40 回复(0)
#include <iostream>
#include <vector>
#include <string>

#define GAME_WIN 1
#define GAME_OVER -1
#define GAME_NORMAL 0

#define DIR_GO 0
#define DIR_COME 1

typedef union{
    uint8_t data;
    struct{
        uint8_t sheep:1;
        uint8_t vegetable:1;
        uint8_t wolf:1;
        uint8_t farmer:1;
    }all;
}Game;

typedef struct{
    uint8_t data;
    int dir;
    int status;
    std::string detail;
}Step;

int check(Game &g) {
    switch(g.data) {
        case 0b0000:
            return GAME_WIN;
        case 0b0111:
        case 0b0101:
        case 0b0011:
        case 0b1000:
        case 0b1010:
        case 0b1100:
            return GAME_OVER;
        default:
            return GAME_NORMAL;
    }
}

int move_sheep(Game &g) {
    if(g.all.farmer == g.all.sheep) {
        g.data ^= 0b1001;
        return g.all.farmer;     // 0 = go, 1 = come
    }
    return GAME_OVER;            // bad move = game over
}

int move_vegetable(Game &g) {
    if(g.all.farmer == g.all.vegetable) {
        g.data ^= 0b1010;
        return g.all.farmer;
    }
    return GAME_OVER;
}

int move_wolf(Game &g) {
    if(g.all.farmer == g.all.wolf) {
        g.data ^= 0b1100;
        return g.all.farmer;
    }
    return GAME_OVER;
}

int move_farmer(Game &g) {
    g.data ^= 0b1000;
    return g.all.farmer;       // 0 = go, 1 = come
}

int next_move(Game &g, int type) {
    switch(type) {
        case 0:
            return move_sheep(g);
        case 1:
            return move_vegetable(g);
        case 2:
            return move_wolf(g);
        case 3:
            return move_farmer(g);
        default:
            return GAME_OVER;
    }
}

std::vector<Step> history;
int dir = 0, status = 0;

void dfs(Game &g) {
    // game over -> return
    if(dir == GAME_OVER || status == GAME_OVER) {
        return;
    }

    // win -> return
    if(status == GAME_WIN) {
        for(int i = 1; i < history.size(); ++i) {         // skip the initial state
            std::cout << history[i].detail << std::endl;
        }
        std::cout << "succeed" << std::endl;
        return;
    }

    // check loop -> return
    for(int i = 0; i < history.size() - 1; ++i) {
        if(history[i].data == g.data)
            return;
    }

    for(int i = 0; i < 4; ++i) {
        // move and check
        dir = next_move(g, i);
        status = check(g);

        // save history
        Step s;
        s.data = g.data;
        s.dir = dir;
        s.status = status;
        switch(i) {
            case 0:
                s.detail = "sheep_";
                break;
            case 1:
                s.detail = "vegetable_";
                break;
            case 2:
                s.detail = "wolf_";
                break;
            case 3:
                s.detail = "nothing_";
                break;
            default:
                break;
        }
        s.detail.append(s.dir == DIR_GO ? "go" : "come");
        history.push_back(s);

        // next step
        dfs(g);

        // backtrack
        history.pop_back();
        g.data = history.back().data;
        dir = history.back().dir;
        status = history.back().status;
    }
}

int main() {
    Game game;
    game.data = 0x0F;       // game init

    Step s;
    s.data=0x0f;
    history.push_back(s);   // history init

    dfs(game);

    return 0;
}

发表于 2022-01-25 01:51:25 回复(0)
import java.util.*;
/**0:农夫, 1:羊, 2:菜, 3:狼*/
public class Main{
    private static int[] status = {0, 0, 0, 0};
    private static boolean flag;
    private static Stack<String> q = new Stack<>();
    private static HashMap<String, Boolean> isExist = new HashMap<>();
    private static String[] info = {"nothing_", "sheep_", "vegetable_", "wolf_"};
    private static String[] way = {"come", "go"};
    public static String state(){
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < 4; i++)
            sb.append(status[i]);
        return new String(sb);
    }
    
    public static boolean Judge(){
        if(status[1] == status[2] && status[1] != status[0])
            return false;
        if(status[1] == status[3] && status[1] != status[0])
            return false;
        return true;
    }
    
    public static void dfs(int x){
        if(status[0] == 1 && status[1] == 1 && status[2] == 1 && status[3] == 1){
            flag = true;
            for(String str : q)
                System.out.println(str);
            System.out.println("succeed");
            return;
        }
        for(int i = 0; i < 4; i++){
            if(status[i] == x)
                continue;
            status[i] = x;
            status[0] = x;
            String curState = state();
            if(isExist.containsKey(curState)){
                status[i] = 1 - x;
                status[0] = 1 - x;
                continue;
            }
            if(Judge()){
                q.add(info[i] + way[x]);
                isExist.put(curState, true);
                dfs(1 - x);
                if(flag)
                    return;
                q.pop();
            }
            else{
                status[i] = 1 - x;
                status[0] = 1 - x;
            }
        }
    }
    public static void main(String[] args){
        dfs(1);
    }
}

发表于 2021-06-16 20:58:02 回复(0)
#include<stdio.h>
void Print(int x){
    switch(x){
        case 1: printf("sheep_go\n");break;
        case 2: printf("sheep_come\n");break;
        case 3: printf("vegetable_go\n");break;
        case 4: printf("vegetable_come\n");break;
        case 5: printf("wolf_go\n");break;
        case 6: printf("wolf_come\n");break;
        case 7: printf("nothing_go\n");break;
        case 8: printf("nothing_come\n");break;
        case 9: printf("succeed\n");break;
        default:printf("Error!\n");
    }
}
int main(){
    Print(1);//农夫带羊过河
    Print(8);//农夫自己回去
    Print(3);//农夫带菜过河
    Print(2);//农夫带羊回去
    Print(5);//农夫带狼过河
    Print(8);//农夫自己回去
    Print(1);//农夫带羊过河
    Print(9);//成功
}

发表于 2021-02-26 16:01:00 回复(0)