写个过河算法
写个过河算法
作者：陈健
警察小偷爸爸妈妈儿子女儿过河，这个游戏不用说的吧，应该很多人见过，一般是考察隔壁邻居家小朋友智商的，有人把他做成了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表示。好了，在对话框类里面加入一个
CArray<InWhere, InWhere> m_wheres;变量记录所有的可能的结点。开始加入了，省去些界面代码：
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(i2) 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<InWhere, InWhere>& 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函数
BOOL Move::Test(CArray<InWhere, InWhere>& p_Ain)
{
//测试某2点是否能够通过
InWhere a = p_Ain.GetAt(m_nNow);
InWhere b = a;
InWhere c = p_Ain.GetAt(m_nNext);
InWhere d = c;
int num(0);
//如果是开始在船上的话
if(a.boat == 2)
{
++num;
}
if(c.boat == 2)
{
++num;
}
//头和尾只能有且有一个在船上
if(num != 1)
return FALSE;
//只要在船上的状态等于岸边的状态就表示此路是行的通的
//从船上到岸上的
if(a.boat == 2)
{
//---*--->*
if(a.daughter1 == 2)
a.daughter1 = 3;
if(a.daughter2 == 2)
a.daughter2 = 3;
if(a.father == 2)
a.father = 3;
if(a.mother == 2)
a.mother = 3;
if(a.plice == 2)
a.plice = 3;
if(a.shife == 2)
a.shife = 3;
if(a.son1 == 2)
a.son1 = 3;
if(a.son2 == 2)
a.son2 = 3;
a.boat =3;
if(a == p_Ain.GetAt(m_nNext))
return TRUE;
//*<----*-----
if(b.daughter1 == 2)
b.daughter1 = 1;
if(b.daughter2 == 2)
b.daughter2 = 1;
if(b.father == 2)
b.father = 1;
if(b.mother == 2)
b.mother = 1;
if(b.plice == 2)
b.plice = 1;
if(b.shife == 2)
b.shife = 1;
if(b.son1 == 2)
b.son1 = 1;
if(b.son2 == 2)
b.son2 = 1;
b.boat =1;
if(b == p_Ain.GetAt(m_nNext))
return TRUE;
}
//从岸到船上
if(c.boat == 2)
{
//----*<---*
if(c.daughter1 == 2)
c.daughter1 = 3;
if(c.daughter2 == 2)
c.daughter2 = 3;
if(c.father == 2)
c.father = 3;
if(c.mother == 2)
c.mother = 3;
if(c.plice == 2)
c.plice = 3;
if(c.shife == 2)
c.shife = 3;
if(c.son1 == 2)
c.son1 = 3;
if(c.son2 == 2)
c.son2 = 3;
c.boat =3;
if(c == p_Ain.GetAt(m_nNow))
return TRUE;
//*---->*----
if(d.daughter1 == 2)
d.daughter1 = 1;
if(d.daughter2 == 2)
d.daughter2 = 1;
if(d.father == 2)
d.father = 1;
if(d.mother == 2)
d.mother = 1;
if(d.plice == 2)
d.plice = 1;
if(d.shife == 2)
d.shife = 1;
if(d.son1 == 2)
d.son1 = 1;
if(d.son2 == 2)
d.son2 = 1;
d.boat =1;
if(d == p_Ain.GetAt(m_nNow))
return TRUE;
}
return FALSE;
}
结束后，好了，一个整图的样子就展现在我们面前了：
就是要这样从1走到20的样子，其实都在CArray<Move, Move> m_MoveAll;里面了
数组里记录了1-》2，2-》4，2-》8，8-》19，7-》100什么的我们要从1找到到20的路并且记录下结点
怎么搞~，我不会，（啪，又一个鸡蛋飞了过来。靠~还来，你等我说完呀，我可以很负责任告诉你，大健很生气，后果很严重）。
开始我也不记得怎么搞了，突然一个声音从天上传过来：你要脑袋干什么，你要那么多书干什么。
我一下厕所顿开，回家翻书……才看了一点，我想到了，我可以来个深度编历。从1开始找找到20就可以了。过程中记得要压栈和出栈。主要函数GORIVER,用一个CArray<int,
int> Road模拟栈。
void CRiverDlg::GoRiver(CArray<int,int>& p_Road, int Begin, int End, CArray<Move, Move>& p_MoveAll, BOOL *Visited)
{
//深度遍历图形算法
//此步不需要因为从设置了结束位以后就再也没调用GORIVER了
//if(m_bEndFlag) return;
int i;
Visited[Begin] = TRUE;
//讲其加入到走过的路中
p_Road.Add(Begin);
if(Begin == End)
{
m_bEndFlag = TRUE;
MessageBox("找到了从起点通往终点道路");
return;
}
for(i=0; i<p_MoveAll.GetSize(); i++)
{
if(p_MoveAll.GetAt(i).m_nNow == Begin)
{
if(Visited[p_MoveAll.GetAt(i).m_nNext] == FALSE)
{
GoRiver(p_Road,
p_MoveAll.GetAt(i).m_nNext,
End,
p_MoveAll,
Visited);
if(m_bEndFlag) return;
}
}
}
//如果遍历完了还没找到说明此路不通出栈
p_Road.RemoveAt(p_Road.GetSize()-1);
}
看懂了吗？不懂~哈哈~回去看书把深度编历。现在知道后果很严重了吧。看死你。详细看看源代码吧。
题外
第2天MM还在玩这个游戏，还在叫到：昨天我才走过去了，今天走又不行了。我奸笑一声扑了过去，对不起，说错了应该是走了过去，寒一个~先叫MM随便走，MM走了N步以后，说实在想不到了，我说好我来，你走到任一步我都能帮你走到幸福的终点，因为你遇见了我了。然后我点开程序，GOGOGO，出来了，照着走哈哈~。搞定。MM很崇拜的看着我，说到：你真行。我眼睛红红的说，那是。其实心里寒了一把（昨天晚上熬了N长时间，就为了你这么一笑，不过有种东西叫成就感，我想你曾经体会到或者现在体会到过或者以后将会体会到）
题外的题外
我不想全写苦力式的业务了，才毕业时的激情都给搞没了。哪位大侠介绍份有前途又有钱途的编程职业给我，我253各位了。我很有潜力的。（哧~哧~哈哈，这次的番茄被我接到了，恩吃一口味道还不错，还有鸡蛋没）EMAIL：LWKL2008@YAHOO.COM.CN
