文物

完成了上面的准备工作，现在的问题变成：

从初始状态二进制0000(全部在河的南岸) 出发，寻找一种全部由安全状态构成的状态序列，它以二进制1111(全部到达河的北岸) 为最终目标，并且在序列中的每一个状态都可以从前一状态通过农夫（可以带一样东西）划船过河的动作到达。

为避免不必要的瞎费功夫，要求在序列中不应该出现重复的状态。为了实现广度优先搜索，算法中需要使用了一个整数队列moveTo，它的每个元素表示一个可以安全到达的中间状态。另外还需要一个数据结构记录已被访问过的各个状态，以及已被发现的能够到达当前这个状态的路径。

由于在这个问题的解决过程中需要列举的所有状态(二进制0000 ~ 1111)一共16种，所以可以构造一个包含16个元素的整数顺序表来满足以上的要求。用顺序表的第i个元素记录状态i是否已被访问过，若已被访问过则在这个顺序表元素中记入前驱状态值，算法中把这个顺序表叫做route。route的每个分量初始化值均为-1，每当我们在队列中加入一个新状态时，就把顺序表中以该状态作下标的元素的值改为达到这个状态的路径上前一状态的下标值。route的一个元素具有非负值表示这个状态已访问过，或是正被考虑。最后我们可以利用route顺序表元素的值建立起正确的状态路径。 五、 程序代码 // farmerProblem.c

// 用队列解决农夫过河问题

#include #include typedef int DataType;

//顺序队列：类型和界面函数声明

struct SeqQueue {

// 顺序队列类型定义

int MAXNUM; // 队列中最大元素个数 int f, r;

DataType *q; };

typedef struct SeqQueue *PSeqQueue; // 顺序队列类型的指针类型

PSeqQueue createEmptyQueue_seq(int m) {

//创建一个空队列

PSeqQueue queue = (PSeqQueue)malloc(sizeof(struct SeqQueue)); if (queue != NULL) {

queue->q = (DataType*)malloc(sizeof(DataType) *m); if (queue->q)

{

queue->MAXNUM = m; queue->f = 0; queue->r = 0; return (queue); } else

free(queue); }

printf(\"Out of space!!\\n\"); // 存储分配失败 return NULL; }