中文XML论坛--过河问题[讨论]

贴子主题：过河问题[讨论]

本主题类别:

终于可以了：）
原来是判断递归结束的四个if语句中，有一句的一个变量名写错了。

typedef struct _stNode {
int hl, bl, hr, br;
pos bp;     /* boat position */
struct _stNode *parent;
} stNode;
bool humbst(stNode st, FILE *fp, void (*opt)(stNode sm, void *fp))
{
bool rev = false;
do
{
  /* 该状态与初始状态相同的情况不操作 */
  if (st.hl == N && st.bl == N && st.hr == 0 &&
   st.br == 0 && st.bp == left && st.parent != NULL)
   break;
  /* 该状态与祖父状态相同的情况不操作 */
  if (st.parent != NULL && st.parent->parent != NULL)
  {
   if ((st.hl == st.parent->parent->hl)
    && (st.bl == st.parent->parent->bl)
    && (st.hr == st.parent->parent->hr)
    && (st.br == st.parent->parent->br)
    && (st.bp == st.parent->parent->bp))
    break;
  }
  /* 人数小于兽数的时候不满足 */
  if ((st.hl != 0 && st.hr != 0 && (st.hl < st.bl || st.hr < st.br))
   || (st.hl != 0 && st.hr == 0 && st.hl < st.bl)
   || (st.hl == 0 && st.hr != 0 && st.hr < st.br))
   break;
  /* 中止状态 */
  if (st.hl == 0 && st.bl == 0 && st.hr == N &&
   st.br == N && st.bp == right)
  {
   opt(st, fp);
   rev = true;
   break;
  }
  /* 正常情况 */
  opt(st, fp);
  switch (st.bp)
  {
  case left:
   rev = humbst_left(st, fp, stDisp);
   break;
  case right:
   rev = humbst_right(st, fp, stDisp);
   break;
  }
} while (false);
return rev;
}
bool humbst_left(stNode st, FILE *fp, void (*opt)(stNode sm, FILE *fp))
{
bool rev = false;
stNode st1, st2, st3, st4, st5;
if (st.hl >= 1) /* 将左边的一个人运到右边 */
{
  st1.hl = st.hl - 1;
  st1.bl = st.bl;
  st1.hr = st.hr + 1;
  st1.br = st.br;
  st1.bp = right;
  st1.parent = &st;
  rev = humbst(st1, fp, opt);
}
if (st.hl >= 2) /* 将左边的两个人运到右边 */
{
  st2.hl = st.hl - 2;
  st2.bl = st.bl;
  st2.hr = st.hr + 2;
  st2.br = st.br;
  st2.bp = right;
  st2.parent = &st;
  rev = humbst(st2, fp, opt);
}
if (st.bl >= 1) /* 将左边的一个兽运到右边 */
{
  st3.hl = st.hl;
  st3.bl = st.bl - 1;
  st3.hr = st.hr;
  st3.br = st.br + 1;
  st3.bp = right;
  st3.parent = &st;
  rev = humbst(st3, fp, opt);
}
if (st.bl >= 2) /* 将左边的两个兽运到右边 */
{
  st4.hl = st.hl;
  st4.bl = st.bl - 2;
  st4.hr = st.hr;
  st4.br = st.br + 2;
  st4.bp = right;
  st4.parent = &st;
  rev = humbst(st4, fp, opt);
}
if (st.hl >= 1 && st.bl >= 1) /* 将左边的一个人一个兽运到右边 */
{
  st5.hl = st.hl - 1;
  st5.bl = st.bl - 1;
  st5.hr = st.hr + 1;
  st5.br = st.br + 1;
  st5.bp = right;
  st5.parent = &st;
  rev = humbst(st5, fp, opt);
}
return rev;
}
bool humbst_right(stNode st, FILE *fp, void (*opt)(stNode sm, FILE *fp))
{
bool rev = false;
stNode st1, st2, st3, st4, st5;
if (st.hr >= 1) /* 将右边的一个人运到左边 */
{
  st1.hl = st.hl + 1;
  st1.bl = st.bl;
  st1.hr = st.hr - 1;
  st1.br = st.br;
  st1.bp = left;
  st1.parent = &st;
  rev = humbst(st1, fp, opt);
}
if (st.hr >= 2) /* 将右边的两个人运到左边 */
{
  st2.hl = st.hl + 2;
  st2.bl = st.bl;
  st2.hr = st.hr - 2;
  st2.br = st.br;
  st2.bp = left;
  st2.parent = &st;
  rev = humbst(st2, fp, opt);
}
if (st.br >= 1) /* 将右边的一个兽运到左边 */
{
  st3.hl = st.hl;
  st3.bl = st.bl + 1;
  st3.hr = st.hr;
  st3.br = st.br - 1;
  st3.bp = left;
  st3.parent = &st;
  rev = humbst(st3, fp, opt);
}
if (st.br >= 2) /* 将右边的两个兽运到左边 */
{
  st4.hl = st.hl;
  st4.bl = st.bl + 2;
  st4.hr = st.hr;
  st4.br = st.br - 2;
  st4.bp = left;
  st4.parent = &st;
  rev = humbst(st4, fp, opt);
}
if (st.hr >= 1 && st.br >= 1) /* 将右边的一个人一个兽运到左边 */
{
  st5.hl = st.hl + 1;
  st5.bl = st.bl + 1;
  st5.hr = st.hr - 1;
  st5.br = st.br - 1;
  st5.bp = left;
  st5.parent = &st;
  rev = humbst(st5, fp, opt);
}
return rev;
}

humbest函数其实就是构造一个状态变迁图（树），然后用opt函数来对该图进行操作（比如说dfs）。在此衷心感谢Logician和phoenixinter热心参与讨论，你们的想法给了我很多提示。^_^


	W 3 C h i n a ( since 2003 ) 旗下站点苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》	78.125ms