app.cpp

一个833分酒问题的求解

#include "App.h"
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <functional>
using namespace std;

const int BOTTLE = 8;
const int GLASS = 3;
const int MOUTH = 4;
enum
{
	Bottle_1 = 1,
	Bottle_2,
	Glass,
	Mouth_1,
	Mouth_2,
	Mouth_3,
	Mouth_4,
	Total
};
struct itrState
{
	long lstate;
	int offset;
	int diretion;
};

App::App() {}

App::~App() {}

void App::StateInit(State &SStart, State SFin)
{
	StateStart = SStart;
	StateFin = SFin;
}

void App::Memorize(const State& st)
{
	tState.push_back(st);
	tPath.push_back(st);
}

bool App::Valid(const State &st)
{
	State temp = st;
	for (int i = Mouth_1; i <= Mouth_4; i++)
		if (temp.GetStateAt(i) > MOUTH)
			return false;
	vector<State>::iterator ite = find(tState.begin(), tState.end(), st);
	if (ite != tState.end())
		if (ite->GetProc() <= st.GetProc())
			return false;
		else
			tState.erase(ite);
	return true;
}

bool App::Do(const State &st)
{
	if (st == StateFin && st.GetProc() <= StateFin.GetProc())
	{
		cout << *this;
		return true;
	}
	return false;
}

void App::Undo(const State &st)
{
	tPath.pop_back();
}

App::Iterator::Iterator(const State &st)
{
	itrState* itrPtr = new itrState;
	itrPtr->lstate = st.GetState();
	itrPtr->offset = st.GetProc();
	itrPtr->diretion = 16;
	ptr = itrPtr;
}

void BottleToGlass(int nBottle, State& st)						// 8 to 3
{
	if (st.GetStateAt(Bottle_1) == st.GetStateAt(Bottle_2)
		&&(nBottle == Bottle_2))
		nBottle = Bottle_1;
	int nGlassCapcity = st.GetStateAt(Glass);
	int nBottleCapcity = st.GetStateAt(nBottle) - (GLASS - st.GetStateAt(Glass));
	if (nBottleCapcity < 0)
	{
		nBottleCapcity = 0;
		nGlassCapcity = st.GetStateAt(Glass) + st.GetStateAt(nBottle);
	}
	else
	{
		nGlassCapcity = GLASS;
	}
	st.SetStateAt(nBottle, nBottleCapcity);
	st.SetStateAt(Glass, nGlassCapcity);
}

void GlassToBottle(int nBottle, State& st)					// 3 to 8
{
	if ((nBottle == Bottle_2)
		&&st.GetStateAt(Bottle_1) == st.GetStateAt(Bottle_2))
		nBottle = Bottle_1;
	int nGlassCapcity = st.GetStateAt(Glass);
	int nBottleCapcity = st.GetStateAt(nBottle) + st.GetStateAt(Glass);
	if (nBottleCapcity > BOTTLE)
	{
		nBottleCapcity = BOTTLE;
		nGlassCapcity = st.GetStateAt(nBottle) + st.GetStateAt(Glass) - BOTTLE;
	}
	else
	{
		nGlassCapcity = 0;
	}
	st.SetStateAt(nBottle, nBottleCapcity);
	st.SetStateAt(Glass, nGlassCapcity);
}

void ContainerToMouth(int nContainer, int nMouth, State& st)		// 3 to 4
{
	if (st.GetStateAt(Bottle_1) == st.GetStateAt(Bottle_2)
		&&nContainer == Bottle_2)
		nContainer = Bottle_1;
	if (nMouth == Mouth_4)
	{
		for (int i = Mouth_1; i < Mouth_4; i++)
		{
			if (st.GetStateAt(i) == st.GetStateAt(Mouth_4))
			{
				nMouth = i;
				break;
			}
		}
	}
	else if (nMouth == Mouth_3)
	{
		for (int i = Mouth_1; i < Mouth_3; i++)
		{
			if (st.GetStateAt(i) == st.GetStateAt(Mouth_3))
			{
				nMouth = i;
				break;
			}
		}
	}
	else if (nMouth == Mouth_2)
	{
		if (st.GetStateAt(Mouth_1) == st.GetStateAt(Mouth_2))
			nMouth = Mouth_1;
	}
	int nContainerCapcity = 0;
	int nMouthCapcity = st.GetStateAt(nContainer) + st.GetStateAt(nMouth);
	st.SetStateAt(nContainer, nContainerCapcity);
	st.SetStateAt(nMouth, nMouthCapcity);
}

State App::Iterator::operator ++(int)
{
	itrState* itrPtr = reinterpret_cast<itrState*>(ptr);
	State nextSt;
	nextSt.SetState(itrPtr->lstate);
	nextSt.SetProc(itrPtr->offset);
	int nDirection = itrPtr->diretion;
	if (nDirection < 3 &&
		(nextSt.GetStateAt(1) + nextSt.GetStateAt(2) < BOTTLE * 2))
	{
		GlassToBottle(nDirection, nextSt);
	}
	else if (nDirection < 5 && nDirection >= 3 && nextSt.GetStateAt(3) < 3)
	{
		BottleToGlass(nDirection - 2, nextSt);
	}
	else if (nDirection < 9 && nDirection >= 5)
	{
		ContainerToMouth(3, nDirection - 1, nextSt);
	}
	else if (nDirection >= 9 && nDirection <= 16)
	{
		ContainerToMouth((nDirection - 5)/4, (nDirection - 5)%4 + 4, nextSt);
	}
	itrPtr->diretion--;
	nextSt.SetProc(nextSt.GetProc() + 1);
	return nextSt;
}

bool App::Iterator::eoi()
{
	itrState* itrPtr = reinterpret_cast<itrState*>(ptr);
	return itrPtr->diretion <= 0;
}

ostream& operator << (ostream& out, App& app)
{
	cout << app.tPath.size() << endl;
	for (vector<State>::iterator ite = app.tPath.begin(); ite != app.tPath.end(); ite++)
	{
		cout << setfill(' ') << setw(2) << setbase(10) << ite->GetProc() << " ";
		cout << setfill('0') << setw(7) << hex << ite->GetState() << endl;
	}
	return out;
}