数据结构与算法笔记：计算思维之经典农夫过河问题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;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131

最终结果

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