题目：
一个农夫带着一只狼，一只羊和一些菜过河。河边只有一条船，由于船太小，只能装下农夫和他的一样东西。在无人看管的情况下，狼要吃羊，羊要吃菜，请问农夫如何才能使三样东西平安过河。
算法的实质：
在满足一定条件下的，所有状态的遍历。
满足的条件：
1.每次农夫必须移动
2.农夫移动的东西与农夫必须在同一岸，但农夫可不带东西独自移动
3.此种状态，必须在以往从来没有出现过
基本思路：
以4位二进制分别表达农夫，狠，菜，羊的状态，1表示在北岸，0表示在南岸。使用队列广度优先遍历所有状态,并记下遍历的可用顺序(重复遍历被除去）
1.队列代码
View Code
#pragma once
/*
* MAX-1 容量的队列
*/
template<class DATA,int MAX>
class Queue
{
public:
Queue(void)
{
m_nFront = 0;
m_nTail = 0;
}
~Queue(void){}
bool Full()
{
if( (m_nTail + 1)%MAX == m_nFront )
{
return true;
}
return false;
}
bool PushBack( DATA data)
{
if(Full())
{
return false;
}
m_data[m_nTail] = data;
m_nTail = (m_nTail+1)%MAX;
return true;
}
bool Empty()
{
if( m_nFront == m_nTail )
{
return true;
}
return false;
}
DATA* GetFront()
{
if( !Empty() )
{
DATA data = m_data[m_nFront];
m_nFront = (m_nFront + 1)%MAX ;
return &data;
}
return NULL;
}
private:
DATA m_data[MAX];
int m_nFront;
int m_nTail;
};
2.农夫过河
View Code
1 //0表示在南岸，1表示在北岸
2 #include "string.h"
3 //按照 农夫，狼，白菜，羊的顺序，排列在一个int中
4 int farmer(int location)
5 {
6 return (location & 0x08)!=0 ;
7 }
8 int wolf(int location)
9 {
10 return (location & 0x04)!=0;
11 }
12 int cabbage(int location)
13 {
14 return (location & 0x02)!=0;
15 }
16 int goat( int location)
17 {
18 return (location & 0x01)!=0;
19 }
20 bool safe(int location)
21 {
22 if(wolf(location)== goat((location)) && goat(location) != farmer(location)){
23 return false;
24 }
25 if(cabbage(location)== goat((location)) && goat(location) != farmer(location)){
26 return false;
27 }
28 return true;
29 }
30 int printResult(int* rout, int len);
31 void farmerProblem()
32 {
33 int rout[16];//是否已经走过这种状态
34 memset(&rout,-1,sizeof(rout));
35 Queue<int ,100> queue;
36 queue.PushBack(0);//全都在南岸的状态
37 int newlocation = 0;
38 while (!queue.Empty() && rout[15] != 1)
39 {
40 int location = *queue.GetFront();
41
42 int b = false;//无与农夫同岸的物品
43 for (int i = 1;i<8;i= i<<1)
44 {
45 if ( farmer(location)== (location& i) )//如果农夫和所移物品在同岸，则可移动
46 {
47 newlocation = location;
48 newlocation ^= i;
49 newlocation ^= 0x08;//农夫移动
50
51 if ( rout[newlocation] == -1 && safe(newlocation))//新状态未入栈，且是安全的，则入栈
52 {
53 rout[location] = newlocation;
54 queue.PushBack(newlocation);
55 printf("%d进栈\n",newlocation);
56 b = true;
57 }
58 }
59 }
60 if (!b)
61 {
62 newlocation = location;
63 newlocation ^= 0x08;//农夫移动
64
65 if ( rout[newlocation] == -1 && safe(newlocation))//新状态未入栈，且是安全的，则入栈
66 {
67 rout[location] = newlocation;
68 queue.PushBack(newlocation);
69 }
70 }
71 }
72 //printResult(rout,sizeof(rout)/sizeof(int));
73 }
74 int printResult(int* rout, int len)
75 {
76 for(int i = 0; i <= len && i >= 0 && rout[i]>=0; i = rout[i])
77 {
78 printf("index:%d num:%d\n",i,rout[i]);
79
80 if(farmer(rout[i])){
81 printf("农民在北岸\n");
82 }
83 else{
84 printf("农民在南岸\n");
85 }
86
87 if(wolf(rout[i]) ){
88 printf("狼在北岸\n");
89 }
90 else{
91 printf("狼在南岸\n");
92 }
93
94 if(cabbage(rout[i]) ){
95 printf("白菜在北岸\n");
96 }
97 else{
98 printf("白菜在南岸\n");
99 }
100
101 if(goat(rout[i]) ){
102 printf("羊在北岸\n");
103 }
104 else{
105 printf("羊在南岸\n");
106 }
107
108 printf("\n\n");
109 }
110 return 0;
111 }
// queue.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include "Queue.h"
#include <stdlib.h>
#include "farmer.h"
int _tmain(int argc, _TCHAR* argv[])
{
farmerProblem();
system("pause");
return 0;
}