|
题目：
有一条河，在河的左岸有3个人和3个野兽要过河。河里有一只船，该船每次最多可以装2个物体（人或兽）。在河两岸上如果人的数目小于兽的数目，人就被兽吃掉。请列出人和兽能安全过河所有方法。
算法分析：
将某一时刻河岸的整个状态抽象为一个结构体，而没一个状态会由下列5中情况派生出5个子状态：1个人过河，2个人过河，1个兽过河，2个兽过河，1个人和一个兽过河。对每一个子状态进行判断：如果左边和右边都有人，两边的人数必须分别大于等于两边的兽数；如果左边有人，右边没人，左边的人数必须大于左边兽数；如果左边没人，右边有人，右边的人数必须大于右边的兽数。考虑用五元组 （X,Y,U,V,Z）建立模型：X-左边人数，Y-左边兽数，U-右边人数，V-右边兽数，Z-船的位置。
算法描述：
/* 状态节点 */
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, FILE *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）。
上面算法描述其实就是代码片断了，思路很清晰。我已经编译通过，只需自己添加opt函数和main函数就可以运行了。
|
