农夫过河问题是上学期数据结构作业之一。我的C语言还处于业余水平，算法和数据结构更是马马虎虎，转专业之前也没做过类似的项目，网上有各种算法和分析，知乎“郑启威”的回答比较清晰，代码写起来也干净利落，花了一晚上消化了基本思路，又自己写了一遍完整的实现。全部使用C语言写的，C++什么的还待学习。

关键点有两个：

• 将问题抽象为数据结构中的“图”，知乎原回答中有比较详细的说明；
• 在此基础上寻找所有的可行路径，主要参考了Uma Priyadarsi在Quora上的思路。

不满意的方面：

在编写过程中尽量避免全局变量，函数之间实现松耦合，然而在结果的输出上并不优雅，将路径保存在了临时数组中，在findPath递归调用过程中就输出了结果，而不是将所有路径转存储然后统一输出。还请看官不吝赐教。

以下是完整代码：

/*农夫过河问题求解*/
#include <stdio.h>
#define NUM_NODES       16
#define TRUE            1
#define FALSE           0
/*二进制位表示左岸人、狼、羊、菜的状态*/
#define HUMAN_BIT       8
#define WOLF_BIT        4
#define SHEEP_BIT       2
#define CABBAGE_BIT     1
/*判断人、狼、羊、菜的状态*/
#define HUMAN(state)    ((state) & HUMAN_BIT)
#define WOLF(state)     ((state) & WOLF_BIT)
#define SHEEP(state)    ((state) & SHEEP_BIT)
#define CABBAGE(state)  ((state) & CABBAGE_BIT)

int main()
{
    void createStateMatrix(int matrix[][NUM_NODES]);
    void removeInvalidState(int matrix[][NUM_NODES]);
    void findPath(int graph[][NUM_NODES], int startNode, int endNode, int depth);
    int matrix[NUM_NODES][NUM_NODES] = { 0 };
    printf("农夫过河问题, 所有方案如下：\n");
    createStateMatrix(matrix);      //构建矩阵
    removeInvalidState(matrix);     //移除非法状态
    findPath(matrix, 15, 0, 0);     //深度优先搜索，显示结果
    return 0;
}
/*构造矩阵，如果两个状态可以互相转换，将矩阵对应的位置设为1。*/
void createStateMatrix(int matrix[][NUM_NODES])
{
    for (int i = 0, j; i < HUMAN_BIT; i++) {
        j = i | HUMAN_BIT;
        matrix[i][j] = matrix[j][i] = 1;
        if (!WOLF(i))
            matrix[i][j | WOLF_BIT] = matrix[j | WOLF_BIT][i] = 1;
        if (!SHEEP(i))
            matrix[i][j | SHEEP_BIT] = matrix[j | SHEEP_BIT][i] = 1;
        if (!CABBAGE(i))
            matrix[i][j | CABBAGE_BIT] = matrix[j | CABBAGE_BIT][i] = 1;
    }
}
/*移除单个非法状态*/
void removeOneInvalidState(int matrix[][NUM_NODES], int state)
{
    for (int i = 0; i < NUM_NODES; ++i){
        matrix[i][state] = matrix[state][i] = 0;
        matrix[i][15 & ~state] = matrix[15 & ~state][i] = 0;
    }
}
/*判断并移除所有非法状态*/
void removeInvalidState(int matrix[][NUM_NODES])
{
    for (int i = 0; i < HUMAN_BIT; ++i)             //只考虑人不在的状态
        if ((WOLF(i) && SHEEP(i)) || (SHEEP(i) && CABBAGE(i))) 
            removeOneInvalidState(matrix, i);
}
/*对图进行深度优先遍历，获取所有1111->0000的路径*/
void findPath(int matrix[][NUM_NODES], int currentNode, int targetNode, int depth)
{
    static int visited[NUM_NODES];     //访问标记
    static int path[NUM_NODES];        //记录路径
    void printResult(int path[], int depth, int count);
    path[depth++] = currentNode;
    if (currentNode == targetNode) {
        static int count = 0;
        count++;                        //计数
        printResult(path, depth, count);//输出结果
    }
    else {
        visited[currentNode] = TRUE;
        for (int j = 0; j < NUM_NODES; ++j)
            if (matrix[currentNode][j] && !visited[j])
                findPath(matrix, j, targetNode, depth);
        visited[currentNode] = FALSE;
        depth--;
    }
}
/*输出结果*/
void printResult(int path[], int depth, int count)
{
    int state, nextState;
    printf("方案%d：农夫", count);
    for (int i = 0; i < depth - 1; ++i) {
        state = path[i];
        nextState = path[i + 1];
        switch (state ^ nextState) {
        case HUMAN_BIT:                 printf("单独"); break;
        case HUMAN_BIT | CABBAGE_BIT:   printf("带菜"); break;
        case HUMAN_BIT | SHEEP_BIT:     printf("带羊"); break;
        case HUMAN_BIT | WOLF_BIT:      printf("带狼"); break;
        default:printf("异常：%d->%d", state, nextState); break;
        }
        printf("%s->", HUMAN(state) ? "过去" : "返回");
    }
    printf("完成！\n");
}