整整作了两个多小时,越写越乱,没作任何exception handling,程序混乱的一塌糊涂。凑合着看吧,排排序应该会快一些,不过已经很快乐。以后有时间再整理。
输入:
CCondition("ENG", "Red", "", "", ""),
CCondition("SWE", "", "Dog", "", ""),
CCondition("DAN", "", "", "Tea", ""),
CCondition("", "Green|White", "", "", "", CONDITION_TYPE_NEIGHBOR_LEFTATTR),
CCondition("", "Green", "", "Coffee", ""),
CCondition("", "", "Bird", "", "PaulMall"),
CCondition("", "Yellow", "", "", "DunHill"),
CCondition("", "", "", "Milk", "", CONDITION_TYPE_LOCATION, 2),
CCondition("NOR", "", "", "", "", CONDITION_TYPE_LOCATION, 0),
CCondition("", "", "Cat", "", "Mix", CONDITION_TYPE_NEIGHBOR_DIFFATTR),
CCondition("", "", "Horse", "", "DunHill", CONDITION_TYPE_NEIGHBOR_DIFFATTR),
CCondition("", "", "", "Beer", "BueMaster"),
CCondition("GER", "", "", "", "Prince"),
CCondition("NOR", "Blue", "", "", "", CONDITION_TYPE_NEIGHBOR_DIFFATTR),
CCondition("", "", "", "Water", "Mix", CONDITION_TYPE_NEIGHBOR_DIFFATTR),
输出:
*********Posibility*************0
Nation=NOR, HouseColor=Yellow, Pet=Cat, Drink=Water, Cigarette=DunHill.
Nation=DAN, HouseColor=Blue, Pet=Horse, Drink=Tea, Cigarette=Mix.
Nation=ENG, HouseColor=Red, Pet=Bird, Drink=Milk, Cigarette=PaulMall.
Nation=GER, HouseColor=Green, Pet=, Drink=Coffee, Cigarette=Prince.
Nation=SWE, HouseColor=White, Pet=Dog, Drink=Beer, Cigarette=BueMaster.
Press any key to continue
#include <iostream>
#include <sstream>
#include <vector>
using namespace std;enum CONDITION_TYPE
{
CONDITION_TYPE_NEIGHBOR_DIFFATTR = 0,
CONDITION_TYPE_EXACT,
CONDITION_TYPE_NEIGHBOR_LEFTATTR,
CONDITION_TYPE_LOCATION,
END_PLUS_ONE_CONDITION_TYPE
};class CCondition
{
public:
CCondition(string sNation, string sHouseColor, string sPet, string sDrink, string sCigarette, int intType=CONDITION_TYPE_EXACT, int intLocation = -1)
: m_intType(intType), m_intLocation(intLocation)
{
m_sAttr[0]=sNation, m_sAttr[1]=sHouseColor, m_sAttr[2]=sPet, m_sAttr[3]=sDrink, m_sAttr[4]=sCigarette;
}
CCondition() : m_intType(-1), m_intLocation(-1) {}
void SeparateNeighbor(CCondition &cd1, CCondition &cd2);
void SeparateLeft(CCondition &cd1, CCondition &cd2);private:
string m_sAttr[5];
int m_intType;
int m_intLocation;friend class CApartment;
friend class CSolution;
};void CCondition::SeparateNeighbor(CCondition &cd1, CCondition &cd2)
{
int intCount;
cd1 = *this;
cd2 = *this;
for (intCount = 0; intCount < 5; intCount++)
{
if (!m_sAttr[intCount].empty())
{
cd1.m_sAttr[intCount] = \"\";
break;
}
}
for (++intCount;intCount < 5; intCount++)
{
if (!m_sAttr[intCount].empty())
{
cd2.m_sAttr[intCount] = \"\";
break;
}
}
}void CCondition::SeparateLeft(CCondition &cd1, CCondition &cd2)
{
int intCount, intPos;
cd1 = *this;
cd2 = *this;
for (intCount = 0; intCount < 5; intCount++)
{
if (!m_sAttr[intCount].empty() && (intPos = m_sAttr[intCount].find('|')) > 0)
{
cd1.m_sAttr[intCount].erase(intPos, cd1.m_sAttr[intCount].size());
cd2.m_sAttr[intCount].erase(0, intPos+1);
break;
}
}
}class CApartment
{
public:
CApartment() {}
void Clear() {for (int intCount=0; intCount < 5; intCount++) m_sAttr[intCount]=\"\";}
bool IsComplete() {for (int intCount=0; intCount < 5; intCount++)
if (!m_sAttr[intCount].empty()) return false; return true;}
bool InsertCondition(CCondition &cd);
string ToString() const;
private:
string m_sAttr[5];
};string CApartment::ToString() const
{
stringstream ssOutput;
ssOutput << \"Nation=\" << m_sAttr[0] << \", HouseColor=\" << m_sAttr[1] << \", Pet=\" << m_sAttr[2]
<< \", Drink=\" << m_sAttr[3] << \", Cigarette=\" << m_sAttr[4] << \".\" << endl;
return ssOutput.str();
};bool CApartment::InsertCondition(CCondition &cd)
{
CApartment aptResult = *this;for (int intCount = 0; intCount < 5; intCount++)
{
if (!m_sAttr[intCount].empty() && !cd.m_sAttr[intCount].empty()
&& m_sAttr[intCount] != cd.m_sAttr[intCount])
return false;
else if (!cd.m_sAttr[intCount].empty())
aptResult.m_sAttr[intCount] = cd.m_sAttr[intCount];
}*this = aptResult;
return true;
};ostream& operator << (ostream &o, const CApartment &apt)
{
return o << apt.ToString();
}
class CSolution
{
public:
bool IsComplete() {for (int intAptCount=0; intAptCount < 5; intAptCount++)
if (!m_apt[intAptCount].IsComplete()) return false; return true;}
void Clear() {for (int intAptCount=0; intAptCount < 5; intAptCount++) m_apt[intAptCount].Clear();}
int CSolution::InsertCondition(CCondition &cd, vector<CSolution> &vecSolution);
string ToString() const;
private:
CApartment m_apt[5];
};string CSolution::ToString() const
{
stringstream ssOutput;
for (int intAptCount = 0; intAptCount < 5; intAptCount++)
ssOutput << m_apt[intAptCount].ToString();
return ssOutput.str();
}int CSolution::InsertCondition(CCondition &cd, vector<CSolution> &vecSolution)
{
int intCount;
CCondition cd1, cd2;
CSolution sol;switch (cd.m_intType)
{
case CONDITION_TYPE_EXACT:
for (intCount = 0; intCount < 5; intCount++)
{
sol = *this;
if (sol.m_apt[intCount].InsertCondition(cd))
vecSolution.push_back(sol);
}
break;
case CONDITION_TYPE_NEIGHBOR_DIFFATTR:
cd.SeparateNeighbor(cd1, cd2);
for (intCount = 0; intCount < 4; intCount++)
{
sol = *this;
if (sol.m_apt[intCount].InsertCondition(cd1) && sol.m_apt[intCount+1].InsertCondition(cd2))
vecSolution.push_back(sol);sol = *this;
if (sol.m_apt[intCount].InsertCondition(cd2) && sol.m_apt[intCount+1].InsertCondition(cd1))
vecSolution.push_back(sol);
}
break;
case CONDITION_TYPE_NEIGHBOR_LEFTATTR:
cd.SeparateLeft(cd1, cd2);
for (intCount = 0; intCount < 4; intCount++)
{
sol = *this;
if (sol.m_apt[intCount].InsertCondition(cd1) && sol.m_apt[intCount+1].InsertCondition(cd2))
vecSolution.push_back(sol);
}
break;
case CONDITION_TYPE_LOCATION:
if (cd.m_intLocation < 0 || cd.m_intLocation >= 5)
break;
sol = *this;
if (sol.m_apt[cd.m_intLocation].InsertCondition(cd))
vecSolution.push_back(sol);
break;
default:
break;
}
return vecSolution.size();
}ostream& operator << (ostream &o, const CSolution &sol)
{
return o << sol.ToString();
}int main(int argc, char* argv[])
{ int intCount, intSource;CCondition cdlist[] =
{
CCondition(\"ENG\", \"Red\", \"\", \"\", \"\"),
CCondition(\"SWE\", \"\", \"Dog\", \"\", \"\"),
CCondition(\"DAN\", \"\", \"\", \"Tea\", \"\"),
CCondition(\"\", \"Green|White\", \"\", \"\", \"\", CONDITION_TYPE_NEIGHBOR_LEFTATTR),
CCondition(\"\", \"Green\", \"\", \"Coffee\", \"\"),
CCondition(\"\", \"\", \"Bird\", \"\", \"PaulMall\"),
CCondition(\"\", \"Yellow\", \"\", \"\", \"DunHill\"),
CCondition(\"\", \"\", \"\", \"Milk\", \"\", CONDITION_TYPE_LOCATION, 2),
CCondition(\"NOR\", \"\", \"\", \"\", \"\", CONDITION_TYPE_LOCATION, 0),
CCondition(\"\", \"\", \"Cat\", \"\", \"Mix\", CONDITION_TYPE_NEIGHBOR_DIFFATTR),
CCondition(\"\", \"\", \"Horse\", \"\", \"DunHill\", CONDITION_TYPE_NEIGHBOR_DIFFATTR),
CCondition(\"\", \"\", \"\", \"Beer\", \"BueMaster\"),
CCondition(\"GER\", \"\", \"\", \"\", \"Prince\"),
CCondition(\"NOR\", \"Blue\", \"\", \"\", \"\", CONDITION_TYPE_NEIGHBOR_DIFFATTR),
CCondition(\"\", \"\", \"\", \"Water\", \"Mix\", CONDITION_TYPE_NEIGHBOR_DIFFATTR),
};
CSolution sol;
vector<CSolution> vecResult1, vecResult2, *pvecSource = &vecResult1, *pvecResult = &vecResult2, *pvecTmp = NULL;pvecSource->push_back(sol);
for (intCount = 0; intCount < sizeof(cdlist)/sizeof(CCondition); intCount++)
{
for (intSource = 0; intSource < (*pvecSource).size(); intSource++)
(*pvecSource)[intSource].InsertCondition(cdlist[intCount], *pvecResult);
pvecSource->clear();
pvecTmp = pvecSource;
pvecSource = pvecResult;
pvecResult = pvecTmp;
}for (intCount = 0; intCount < (*pvecSource).size(); intCount++)
{
cout << \"*********Posibility*************\" << intCount << endl << (*pvecSource)[intCount];
}return 0;
}
http://myajax95./