ID #5733

写个过河算法

警察小偷爸爸妈妈儿子女儿过河,这个游戏不用说的吧,应该很多人见过,一般是考察隔壁邻居家小朋友智商的,有人把他做成了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(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<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:[email protected]

本文配套源码


2011-07-01 18:29
阅读:
I'm VC , Just U know Y
本站部分文章来源于互联网,版权归原作者所有。

延伸阅读:

老调重提,利用SDK实现迷宫算法

几个数字信号处理算法程序

CRC算法与实现

牛顿和拉格朗日插值算法

图像分割相关算法