有3个野人和3个传教士来到河边渡河，河岸有一条船，每次至多可供2人乘渡，野人和传教士都会划船。在河岸，如果野人人数多于传教士人数，则野人会吃掉传教士。要求输出所有可能的过程。
答案一共有四个结果，为什么我这个只能算出来一种，望各位解惑。
#ifndef HEAD_H_
#define HEAD_H_
#include<vector>
using namespace std;
class Guohe
{
public:
Guohe(int xx, int yy, bool zz) :x(xx), y(yy), z(zz) {} //构造函数
bool operator==(const Guohe& g) const; //重载==运算符
int getx(); //获取船所在岸边野人数量
int gety(); //获取船所在岸边传教士数量
bool getz() { return z; }; //获取船的位置
bool safe(Guohe& g) const; //判断状态是否安全
void yidong(Guohe& g); //船的移动
friend void gh(Guohe& a, const Guohe& b); //友元函数
private:
int x, y; //野人、传教士数量(左岸)
bool z; //true为船在左岸，false为船在右岸
};
class Gc
{
public:
Gc(int x, int y);
Gc();
void weicha(const int x, const int y); //末尾添加元素
int ssize() { return a.size(); }
bool operator==(const Gc& g) const; //重载==运算符
void pop(); //删除最后一个元素
void print(); //输出函数
void fuzhi(const Gc& g); //复制函数
private:
vector<int>a, b;
};
#endif
#include<iostream>
#include"head.h"
int Guohe::getx()
{
if (z)
return x;
else
return 3 - x;
}
int Guohe::gety()
{
if (z)
return y;
else
return 3 - y;
}
bool Guohe::operator==(const Guohe& g) const
{
if (this->x == g.x && this->y == g.y&&this->z==g.z)
return true;
else
return false;
}
bool Guohe::safe(Guohe& g) const
{
bool b = false;
if (g.y == 0 || g.y == 3)
b = true;
else
{
if (g.x <= g.y && (3 - x <= 3 - y))
b = true;
}
return b;
}
void Guohe::yidong(Guohe& g)
{
if (g.z)
g.z = false;
else
g.z = true;
}
Gc::Gc(int x, int y)
{
a.push_back(x);
b.push_back(y);
}
Gc::Gc()
{
a.push_back(0);
b.push_back(0);
}
bool Gc::operator==(const Gc& g) const
{
if (this->a == g.a && this->b == g.b)
return true;
else
return false;
}
void Gc::weicha(const int x, const int y)
{
a.push_back(x);
b.push_back(y);
}
void Gc::pop()
{
a.pop_back();
b.pop_back();
}
void Gc::print()
{
for (int i = 1; i < a.size(); i++)
{
//cout << b[i] << " " << a[i] << endl;
if (i % 2 == 1)
cout << "左岸到右岸，传教士过去" << b[i] << "人,野人过去" << a[i] << "人" << endl;
else
cout << "右岸到左岸，传教士过去" << b[i] << "人,野人过去" << a[i] << "人" << endl;
}
}
void Gc::fuzhi(const Gc& g)
{
this->a = g.a;
this->b = g.b;
}
#include<iostream>
#include"head.h"
int m1, m2, n1, n2; //m、n为船上野人和传教士数量
int i = 0;
Gc gc[10];
void gh(Guohe& a, const Guohe& b)
{
if (a.z) //左岸到右岸
{
for (m1 = 0; m1 <= 2 && m1 <= a.x; m1++)
{
n1 = 2 - m1;
if (n1 <= a.y)
{
a.x = a.x - m1;
a.y = a.y - n1;
if (a.safe(a))
{
gc[i].weicha(m1, n1);
a.yidong(a);
if (a == b) //终止条件
{
i++;
gc[i].fuzhi(gc[i - 1]);
return;
}
else
{
gh(a, b);
gc[i].pop();
}
}
else
{
a.x = a.x + m1;
a.y = a.y + n1;
}
}
}
}
else //右岸到左岸
{
for (m2 = 0; m2 <= 2 && m2 <= a.getx(); m2++)
{
for (n2 = 0; n2 <= 2 - m2 && n2 <= a.gety(); n2++)
{
if (m2 + n2 == 0 || (m2 == m1 && n2 == n1)) //避免陷入循环
{}
else
{
a.x = a.x + m2;
a.y = a.y + n2;
if (a.safe(a))
{
gc[i].weicha(m2, n2);
a.yidong(a);
gh(a, b);
gc[i].pop();
}
else
{
a.x = a.x - m2;
a.y = a.y - n2;
}
}
}
}
}
}
int main()
{
Guohe t(3, 3, true); //初始状态
Guohe f(0, 0, false); //最终状态
gh(t, f);
for (int ii = 0; ii <= i; ii++)
{
cout << "第" << ii + 1 << "种结果：" << endl;
gc[ii].print();
cout << endl << endl << endl;
}
return 0;
}
