（1）项目描述
游戏规则：一家6口（爸爸、妈妈、两个女儿、两个儿子）及警察和小偷要从河这边渡到河对岸。在河这边仅有一艘小舢板可以把他们载到对岸。可是，只有爸爸、妈妈和警察能够驾船，不论成人与小孩，每程只能承载二人。在渡河过程中，你要避免以下三种情况的发生：
（1）当警察与小偷分开时，小偷会伤害一家6口；
（2）当爸爸看见妈妈离开时，爸爸便会教训女儿；
（3）当妈妈看见爸爸离开时，妈妈便会教训儿子。
（2）解决思路
【数据结构建模】
一共八个人，每个人都有两个状态（左岸和右岸）。我们把八个人在左岸的状态记为[0,0,0,0,0,0,0,0]，都在右岸时记为[1,1,1,1,1,1,1,1]。那么，本项目其实就是要寻找一个从[0,0,0,0,0,0,0,0,0]到[1,1,1,1,1,1,1,1]的解。
这个状态我们其实可以开辟一个8个元素的数组。另外还需要设置一个变量代表船的状态。因为还要打印结果，所以在搜索的过程中还需要一个结构体数组存储每次渡河的人是谁（可能是一个人，也可能是2个人），当然，也可以建立2个一维数组代替结构体数组。
接下来可以选择深度优先搜索或者宽度优先搜索来进行搜索，每个状态的限制条件根据题意可以得出。
最后遍历存储渡河人员的数组，并打印出结果。
其实每个人的状态（包括船的状态都是0或者1），所以其实用一个int型 就可以了。状态转移全部使用位运算。
【建立模型】
使用2的整数次幂表示不同人，所以使用一个整数表示当前的局面， 255为初始，0为结束。
{POLICE=0x80,THIEF=0x40,DAD=0x20,BOY1=0x10,BOY2=0x8,MOM=0x4,GIRL1=0x2,GIRL2=0x1,ALL=0xff,OK=0};
（3）问题扩展
将数组存储状态，变换为用一个字节来表示各个人的状态，然后采用位运算方式进行升级。
可以使用搜索算法（例如广度优先搜索），列出所有可能的状态，并验证每个状态是否符合游戏规则。每个状态可以描述船上和船外的人员。
例如，一种可能的状态可以是：船上是爸爸和一个女儿，船外是妈妈，两个儿子和警察。如果这个状态满足游戏规则，则继续考虑下一个状态。如果不满足，则该状态应被排除。
程序递归地生成新状态，直到找到一种状态，该状态表示所有人都已经到达了对岸，且满足游戏规则。
#include <stdio.h>
#include <stdlib.h>
#define LEFT 0
#define RIGHT 1
const int N = 6;
int people[N] = {1, 1, 1, 0, 0, 0}; // 1代表在左边，0代表在右边
int boat = LEFT;
// 打印当前船的状态，1代表船在左边，0代表船在右边
void print_boat() {
printf("Boat: %d\n", boat);
}
// 打印当前人的状态，1代表在左边，0代表在右边
void print_people() {
printf("People: ");
for (int i = 0; i < N; i++) {
printf("%d ", people[i]);}
printf("\n");
}
// 移动船，direction为LEFT表示船移动到左边，为RIGHT表示船移动到右边
void move_boat(int direction) {
boat = direction;
}
// 判断是否可以移动两个人，如果可以则移动
int move_two_people(int from, int to) {
int count = 0;
for (int i = 0; i < N; i++) {
if (people[i] == from) {
count++;
people[i] = to;
}
if (count == 2) {
break;
}
}
if (count == 2) {
return 1;
}
return 0;
}
int main() {
int i, j, k;
for (i = 0; i < N; i++) {
for (j = 0; j < N; j++) {
for (k = 0; k < N; k++) {
if (people[i] == LEFT && people[j] == LEFT && people[k] == LEFT && boat == LEFT) {
// 爸爸、妈妈、警察在左边，船在左边
if (move_two_people(LEFT, RIGHT)) {
move_boat(RIGHT);
// 判断是否出现以下三种情况的任意一种
if ((people[0] == LEFT && people[1] == RIGHT) ||
(people[2] == LEFT && people[3] == RIGHT) ||(people[4] == LEFT && people[5] == RIGHT))
{
return 1;
}
if ((people[0] == RIGHT && people[2] == RIGHT) ||
(people[0] == RIGHT && people[3] == RIGHT) ||
(people[1] == RIGHT && people[2] == RIGHT) ||
(people[1] == RIGHT && people[3] == RIGHT) ||
(people[4] == RIGHT && people[5] == RIGHT))
{
return 1;
}
return 0;// 其中，people数组用来存储每个人的位置，LEFT表示左岸，RIGHT表示右岸。
// 此代码检查是否出现警察和小偷在不同的岸边的情况或是否有两个以上的人在右岸的情况。