控制台编程

开发平台：
Visual C++

river.cpp：源码内容
							
/************************************************************************/
/*             解决商人渡河问题                                         */
/************************************************************************/
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <stack>
using namespace std;
class CPoint
{
public:
	CPoint(int a = -1, int b = -1) :x(a), y(b) {}
	CPoint(const CPoint& pt): x(pt.x), y(pt.y) {}
	CPoint& operator=(const CPoint &pt)
	{
		x=pt.x;
		y=pt.y;
		return *this;
	}
	int x;
	int y;
};
/////////////////////////////////////////////////////////////////////////////
//
inline bool operator==(const CPoint &pt1, const CPoint& pt2)
{ 
	return pt1.x==pt2.x && pt1.y==pt2.y; 
}
inline bool operator!=(const CPoint &pt1, const CPoint& pt2)
{ 
	return pt1.x!=pt2.x || pt1.y!=pt2.y; 
}
inline CPoint operator+(const CPoint& pt1, const CPoint& pt2)
{ 
	return CPoint(pt1.x+pt2.x, pt1.y+pt2.y); 
}
inline CPoint operator-(const CPoint& pt1, const CPoint& pt2)
{
	return CPoint(pt1.x-pt2.x, pt1.y-pt2.y); 
}
inline ostream& operator<<(ostream &out, const CPoint &pt)
{
	out << '(' << pt.x << ',' << pt.y << ')';
	return out;
}
//
///////////////////////////////////////////////////////////////////////////
// input
void print(vector<CPoint>& st)
{
	for(vector<CPoint>::iterator it = st.begin(); it != st.end(); ++it)
	{
	
		cout << *it;
	}
	cout << endl << endl;
}
/*
 *	Param k: 第K步
 *  Param pt1: 第k-1步时A岸状态
 *  Param pt2: 第k-1步时B岸状态
 *  Param pt4: A岸的终止点状态
 *  Param state: 允许状态数组
 *  Param dec: 允许决策数组
 *  Param avec: A岸已出现过的状态，不允许再出现
 *  Param avec: B岸已出现过的状态，不允许再出现
 *  return: 解决方案的个数
 */
int step(int k, CPoint& pt1, CPoint& pt2, CPoint& pt4,
		  vector<CPoint>& state, vector<CPoint>& dec, vector<CPoint>& avec, vector<CPoint>& bvec)
{
	static vector<CPoint> st; //存储每一次决策
	static int cnt = 0;
	if(pt1 == pt4)
	{
		++cnt;
		print(st); //输出每一次决策
		return cnt; //返回方法的种数
	}
	
	CPoint pt5 = pt1, pt6 = pt2; //pt5--state of land-A, pt6--state of land-B
	CPoint pt3;
	for(vector<CPoint>::iterator it = dec.begin(); it != dec.end(); ++it)
	{
		if(k%2) //A-->B
			pt3 = pt2 + *it;
		else //B-->A
			pt3 = pt1 + *it;
		if(find(state.begin(), state.end(), pt3) != state.end())
		{
			if(k%2 && find(bvec.begin(), bvec.end(), pt3) != bvec.end()) //A-->B
				continue;
			if(k%2==0 && find(avec.begin(), avec.end(), pt3) != avec.end()) //B-->A
				continue;
			if(k%2) //A-->B
			{
				pt5 = pt1 - *it; 
				pt6 = pt2 + *it;
			}
			if(k%2==0) //B-->A
			{
				pt5 = pt1 + *it;
				pt6 = pt2 - *it;	
			}
			if(k%2)//A-->B
				bvec.push_back(pt6);
			else
				avec.push_back(pt5);
			st.push_back(*it);
			step(k+1, pt5, pt6, pt4, state, dec, avec, bvec);
			st.pop_back();
			if(k%2)//A-->B
				bvec.pop_back();
			else 
				avec.pop_back();
		}
	}
	return cnt;//返回方法的种数
}
int main()
{
//MerchantNum--商人数,ServantNum--随从数, 
//Cnt1--仆人比商人多Cnt1时发生抢劫, Cnt2--船的最大负荷
	const int MerchantNum = 3, ServantNum = 3, Cnt1 = 0, Cnt2 = 2;
//允许状态向量
	vector<CPoint> state;
	int i = 0;
	for(; i <= MerchantNum; ++i) //生成状态向量
		for(int j = 0; j <= ServantNum; ++j)
		{
			if(!(j-i > Cnt1 || (ServantNum-j) - (MerchantNum-i) > Cnt1) || !i || MerchantNum==i)//不发生抢劫的情况
				state.push_back(CPoint(i, j));
		}
//允许决策向量
	vector<CPoint> dec;
	for(i = 0; i <= MerchantNum; ++i)//生成决策向量
		for(int j = 0; j <= ServantNum; ++j)
		{
			if(j+i <= Cnt2 && i+j >= 1)
				dec.push_back(CPoint(i, j));
		}
//pt1为land-A的初始情况，pt2为land-B的初始情况，pt4为land-A的终止情况
	CPoint pt1(MerchantNum, ServantNum), pt2(0,0), pt4(0,0);
	vector<CPoint> avec, bvec;
	avec.push_back(CPoint(MerchantNum,ServantNum));
	int n = step(1, pt1, pt2, pt4, state, dec, avec, bvec);
	cout << n << endl;
	return 0;
}

						