写个过河算法

【 tulaoshi.com - C语言心得技巧 】

写个过河算法

作者：陈健

下载源代码

　　警察小偷爸爸妈妈儿子女儿过河，这个游戏不用说的吧，应该很多人见过，一般是考察隔壁邻居家小朋友智商的，有人把他做成了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;//儿子1int son2;//儿子2int daughter1;//女儿1int daughter2;//女儿2int shife;//土匪（CS打多了，称号改不过来了）InWhere & operator =(const InWhere &other);BOOL operator ==(const InWhere &other);BOOL operator !=(const InWhere &other);InWhere();virtual ~InWhere();};      

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;}}     

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;}re