数据结构与算法笔记：计算思维之经典农夫过河问题C++实现

农夫、羊、狼、菜的过河问题

问题描述

• 角色：农夫，羊，狼，菜
• 条件1：船很小，只能装下农夫和其他一个角色
• 条件2：无人看管，羊吃菜，狼吃羊
• 问：如何让其他三种角色被农夫平安带着过河?

相关分析

• 我们可以先用人脑尝试一下相关渡河策略
  • 1 ) 先渡狼，人回来再渡菜，人回来再渡羊
  • 2 ) 先渡菜，人回来再渡狼，人回来再渡羊
  • 以上两种很好想到，而且我们可以知道羊这种角色是不能先渡河过去的，羊需要最后再渡
  • 如果先渡了羊了，之后再渡任何其他角色，都要将羊带回来
  • 可以参考小游戏：http://gameschool.cc/game/178 自己尝试一下
• 我们需要让计算机来计算出来可行的方案
  • 使用策略：枚举
  • 相关算法设计
    • 解决问题的算法有很多种，这里仅提供一种
    • 将此问题抽象为状态和行为的变化
    • 以渡河与否作为判断状态条件
    • 未渡河(在河岸的一侧)状态：0，行为：0
    • 渡河(到河岸的另一侧)状态：1，行为：1
    • 算法是切换各个角色的渡河与未渡河状态进行枚举，得到最终结果(一种可行的方案)

算法实现

#include <cstdio>
#include <cassert>
#include <cstring>

// 状态值只有两种 0, 1
struct  State {
    int h; // 人 human
    int w; // 狼 wolf
    int s; // 羊 sheep
    int v; // 菜 vegetable
};

// 渡河函数
State pass(State s, char role) {
    // 切换人的状态
    s.h =  1 - s.h;
    if(role == '-') {
        // do nothing
    } else if(role == 'W') {
        // 渡狼 切换狼的状态
        s.w = 1 - s.w;
    } else if(role == 'S') {
        // 渡羊 切换羊的状态
        s.s = 1 - s.s;
    } else if(role == 'V') {
        // 渡菜 切换菜的状态
        s.v = 1 - s.v;
    } else {
        // 直接崩溃，方便调试
        assert(0);
    }
    return s;
};

// 标记已尝试的策略
bool passed[2][2][2][2];

// 检测状态是否合法
bool invalid_state_check(State s) {
    // 人和羊不在一边，且羊和狼在一起
    if(s.h != s.s && s.s == s.w) return true;
    // 人和羊不在一边，且羊和菜在一起
    if(s.h != s.s && s.s == s.v) return true;
    return false;
};

// 检测是否为最终状态
bool final_state_check(State s) {
    // 最终状态为:人,狼,羊,菜都已渡河
    if(s.h == 1 && s.w == 1 && s.s == 1 && s.v == 1) return true;
    return false;
};

// 结果集 开辟一个较大的空间
char result[1000];

// 打印结果
void print_result(int step) {
    for(int i = 0; i < step; i++) {
        if(i != 0) {
            printf(" ");
        }
        printf("H");
        if(result[i] != '-') {
            printf("%c", result[i]);
        }
    }
   puts("");
};

// 开始尝试 false 停止
bool go(State s, int step) {
	// 调试输出
    // printf("%d %d %d %d\n", s.h, s.w, s.s, s.v);
    // 判断是否合法
    if(invalid_state_check(s)) {
        return false;
    };

    // 判断是否最终
    if(final_state_check(s)) {
        // 打印结果
        print_result(step);
        return true;
    };

    // 判断是否已经尝试
    if(passed[s.h][s.w][s.s][s.v]) {
        return false;
    };

    // 标记已尝试策略
    passed[s.h][s.w][s.s][s.v] = true;

    // 处理下一个状态 next state
    State ns;
    ns = pass(s, '-');
    result[step] = '-';
    if(go(ns, step+1)) return true;

    // 渡狼
    if(s.h == s.w) {
        result[step] = 'W';
        ns = pass(s, 'W');
        if(go(ns, step+1)) return true;
    };
    
    // 渡羊
    if(s.h == s.s) {
        result[step] = 'S';
        ns = pass(s, 'S');
        if(go(ns, step+1)) return true;
    };
    
    // 渡菜
    if(s.h == s.v) {
        result[step] = 'V';
        ns = pass(s, 'V');
        if(go(ns, step+1)) return true;
    };

    return false;
};

// main函数
int main() {
    memset(passed, 0, sizeof(passed));
    State init_state = {0, 0, 0, 0};
    go(init_state, 0);
    return 0;
};

最终结果

• 输出：HS H HW HS HV H HS
• 解释：先渡羊，人单独回来，再渡狼，人带着羊回来，再渡菜，人回来，最后渡羊