分类： C/C++
2008-04-23 21:56:25
写个过河算法
作者：
警察小偷爸爸妈妈儿子女儿过河，这个游戏不用说的吧，应该很多人见过，一般是考察隔壁邻居家小朋友智商的，有人把他做成了FLASH游戏。规则如游戏图。详细请看文件中那个FLASH游戏
：
那天看见MM在玩，一不小心说漏了嘴，为了让她不鄙视我，只有研究下算法了。
先来分析整个过程，想想怎么用程序实现。好了，经过了1/6小时后想到了种办法，用图来实现之。不能怪我呀，我现在天天写业务，数据结构忘的差不多了。（说话间飞来了个臭番茄，别砸我，我不说废话了，我交代）。
规划下，将游戏中所有人站的位置考虑成一个一个结点，那么我们整个游戏过程就是结点间连同图状。就是从
警察左 土匪左 爸爸左 妈妈左 儿子1左 儿子2左 女儿1左 女儿2左
连通到
警察右 土匪右 爸爸右 妈妈右 儿子1右 儿子右 女儿1右 女儿2右
中间有好多其他结点来提供进行一步一步的移动。为了体现面向对象的设计方法，我来用类实现她LET''S DO
IT（又飞过来个番茄，好了我说中文了，OK）
然而理想和现实是有差距的，实践是检验真理的唯一标准，经过我N长时间实践过以后，明白了光靠左右2个状态值是不行的，经过改进后，类变成了如下形式。
首先是结点类，InWhere
定义如下：
class InWhere
{
public:
int boat; //船的位置，开始没有加这个，后来发现因为没有人在左边时候船在右边的话
//////////////////////////////////////////////////////////////////////////////
// 这种情况不存在，而且也容易产生错误。（船说到~靠，你以为我不是人就不叫
// 对象了吗，小看我，U should be sorry tu me.好了我知道错了，开始没考虑你我浪
// 费了好多时间了，已经受到精神上惩罚了，不要再肉体了）
//////////////////////////////////////////////////////////////////////////////
BOOL Test();//测试是否能符合结点条件
int father;//爸爸
int mother;//妈妈
int plice;//警察
int son1;//儿子1
int son2;//儿子2
int daughter1;//女儿1
int daughter2;//女儿2
int shife;//土匪（CS打多了，称号改不过来了）
InWhere & operator =(const InWhere &other);
BOOL operator ==(const InWhere &other);
BOOL operator !=(const InWhere &other);
InWhere();
virtual ~InWhere();
};
各个状态如下，左边用1表示，中间用2表示，右边用3表示。好了，在对话框类里面加入一个InWhere where; //临时结点
int i,j,k,l,m,n,o,p,q;
for(i=1; i<4; i )
for(j=1; j<4; j )
for(k=1; k<4; k )
for(l=1; l<4; l )
for(m=1; m<4; m )
for(n=1; n<4; n )
for(o=1; o<4; o )
for(p=1; p<4; p )
for(q = 1; q<4; q )
{
where.daughter1 = i;
where.daughter2 = j;
where.father = k;
where.mother = l;
where.plice = m;
where.shife = n;
where.son1 = o;
where.son2 = p;
where.boat = q;
if(where.Test())
{
m_wheres.Add(where);
AccordNum;
nItem;
}
}
最重要的是InWhere::Test()函数，如下：
BOOL InWhere::Test()
{
//测试符合场景状况的结点状态
//必须要有个会驾船的和船在一边
if(father !=boat && mother !=boat && plice !=boat)
return FALSE;
//如果有人在船上那么船必须为2
//船上最多有2个人而且必须有个m_bCanDriver = TRUE的
int i = 0;
if(daughter1 == 2) i ;
if(daughter2 == 2) i ;
if(son1 == 2) i ;
if(son2 == 2) i ;
if(father == 2) i ;
if(mother == 2) i ;
if(plice == 2) i ;
if(shife == 2) i ;
if(i>2) return FALSE;
if(i != 0 && boat != 2)
return FALSE;
//警察和小偷不在一起时候，小偷会伤害家人
if(shife != plice)
{
if(daughter1 == shife || daughter2 == shife ||
son1 == shife || son2 == shife ||
father == shife || mother == shife)
return FALSE;
}
//当爸爸妈妈不在一起时，妈妈骂儿子，爸爸骂女儿
if(mother != father)
{
if(daughter1 == father || daughter2 == father ||
son1 == mother || son2 == mother)
return FALSE;
}
return TRUE;
}
TRUE表示这样的结点符合情况，好了结点加完了。都在m_wheres里面了现在开始找道路，就是各个结点间的连线。继续面向对象。
移动类，同样如下:
class Move
{
public:
BOOL Test(CArray& p_Ain);//测试能否走的通的函数
int m_nNext; //下次到达的结点编号
int m_nNow; //记录目前所在的结点编号
Move();
virtual ~Move();
};
一如下
for(i = 0; i< m_wheres.GetSize(); i )
for(j = 0; j< m_wheres.GetSize(); j )
{
mov.m_nNow = i;
mov.m_nNext = j;
if(i != j && mov.Test(m_wheres))
{
m_MoveAll.Add(mov);
}
}
去掉界面代码主要代码如上，最重要还是Move::Test函数
