人狼羊菜过河_C

人狼羊菜过河

【题目描述】
一个人要将一匹狼、一只羊、一筐菜运到河对岸，但是他的船太小了，一次只能带一样过河。

当他不在时，狼要吃羊、羊要吃菜。

他怎样才能安全地将狼、羊、菜都运过河呢？
请编写程序，找出过河的全部方案。

用 4 个字母分别表示人、狼、羊、菜的状态：

用 M 表示人在，用 . 表示人不在
用 W 表示狼在，用 . 表示狼不在
用 G 表示羊在，用 . 表示羊不在
用 C 表示菜在，用 . 表示菜不在

用 -> 表示船将从左岸去右岸，用 <- 表示船将从右岸去左岸。

举例说明：
若人狼羊菜全在左岸，则状态表示为

MWGC -> ....

若人将羊运到右岸，左岸只剩狼和菜，则状态表示为

.W.C <- M.G.

输入格式

初始状态
终止状态

输出格式

若有解，则输出所有解法。每一个解法由若干行组成，每行表示一个状态。不同的解法之间空一行。若无解，则输出 None。

要求：输出的解法中不允许出现两行相同的状态。

输入样例1

MWGC -> ....
.... <- MWGC

输出样例1

MWGC -> ....
.W.C <- M.G.
MW.C -> ..G.
...C <- MWG.
M.GC -> .W..
..G. <- MW.C
M.G. -> .W.C
.... <- MWGC

MWGC -> ....
.W.C <- M.G.
MW.C -> ..G.
.W.. <- M.GC
MWG. -> ...C
..G. <- MW.C
M.G. -> .W.C
.... <- MWGC

输入样例2

.W.. <- M.GC
M.GC -> .W..

输出样例2

.W.. <- M.GC
MWG. -> ...C
..G. <- MW.C
M.GC -> .W..

.W.. <- M.GC
MW.C -> ..G.
...C <- MWG.
M.GC -> .W..

输入样例3

MWG. -> ...C
MWG. -> ...C

输出样例3

None

输出样例4

MWG. -> ...C
.WG. -> M..C

输出样例4

None

注：为使输出的解法排列顺序一致，要求人每次渡河时都按以下顺序进行探索：

直接过河(不带任何东西)
带狼过河
带羊过河
带菜过河

解题思路
编写一个状态类，类里面有四个bool类型，表示人狼羊菜在左右岸的情况。

利用深度优先遍历的思路解题，每走一步 *** 作就往容器vector存放一个当前状态，由于要求输出的解法中不允许出现两行相同的状态，因此在放入前，检查当前状态是否存在过。

当走到和输出状态一样的时候，输出容器里面所有存放的状态。

其实解题思路在题目最后有提示，所以DFS的判断顺序就是直接过河，带狼过河，带羊过河，带菜过河。

C++代码

#include
#include 

using namespace std;

struct state {
    bool m, w, g, c;

    state() {
        m = w = g = c = false;   //false表示在左边
    }

    //从字符串读取数据
    void setData(string str) {
        if (str[0] == 'M') m = false;
        else m = true;
        if (str[1] == 'W') w = false;
        else w = true;
        if (str[2] == 'G') g = false;
        else g = true;
        if (str[3] == 'C') c = false;
        else c = true;
    }

    //判断当前 *** 作是否合理
    bool beOk() {
        if (m != w && w == g)
            return false;
        if (m != g && g == c)
            return false;
        return true;
    }

    //比较是否相同
    bool comp(state s) {
        if (m == s.m && w == s.w && g == s.g && c == s.c)
            return true;
        return false;
    }

    //打印当前的 *** 作
    void print_state() {
        if (!m) putchar('M'); else putchar('.');
        if (!w) putchar('W'); else putchar('.');
        if (!g) putchar('G'); else putchar('.');
        if (!c) putchar('C'); else putchar('.');
        putchar(' ');
        if (!m) cout << "->"; else cout << "<-";	//通过判断人的位置输出箭头方向
        putchar(' ');
        if (m) putchar('M'); else putchar('.');
        if (w) putchar('W'); else putchar('.');
        if (g) putchar('G'); else putchar('.');
        if (c) putchar('C'); else putchar('.');
        cout << endl;
    }
};

state s_start;
state s_end;
string m_start, m_end;
int flag;
vector<state> vx;

bool find_s(state cur) {	//判断当前 *** 作是否有过
    for (auto &i :vx) {
        if (i.comp(cur))
            return false;
    }
    return true;
}

void vector_print() {		//循环输出 *** 作列表
    if (flag)
        cout << endl;
    for (auto &i : vx)
        i.print_state();
    flag = 1;
}

void dfs(state s_cur) {
    if (s_cur.comp(s_end)) {
        vector_print();
        return;
    }

    state next = s_cur;
    next.m = !s_cur.m;              //直接过河
    if (next.beOk() && find_s(next)) {
        vx.push_back(next);
        dfs(next);
        vx.pop_back();
    }

    next = s_cur;
    if (next.m == next.w) {           //人狼同边,带狼过河
        next.m = !s_cur.m;
        next.w = !s_cur.w;
        if (next.beOk() && find_s(next)) {
            vx.push_back(next);
            dfs(next);
            vx.pop_back();
        }
    }

    next = s_cur;
    if (next.m == next.g) {           //人羊同边,带羊过河
        next.m = !s_cur.m;
        next.g = !s_cur.g;
        if (next.beOk() && find_s(next)) {
            vx.push_back(next);
            dfs(next);
            vx.pop_back();
        }
    }

    next = s_cur;
    if (next.m == next.c) {           //人菜同边,带菜过河
        next.m = !s_cur.m;
        next.c = !s_cur.c;
        if (next.beOk() && find_s(next)) {
            vx.push_back(next);
            dfs(next);
            vx.pop_back();
        }
    }
}

int main() {
    getline(cin, m_start);
    getline(cin, m_end);
    s_start.setData(m_start);
    s_end.setData(m_end);
    
    if (s_start.comp(s_end) || !s_start.beOk()) {	//判断初始状态和终止状态是否相同，或者初始状态不合理
        cout << "None";
        return 0;
    }

    flag = 0;
    state s_cur = s_start;
    vx.push_back(s_cur);                    //push
    dfs(s_cur);
    vx.pop_back();                          //pop

    if (!flag)
        cout << "None";
    return 0;
}