转自：http://blog.csdn.net/huangxy10/article/details/8066408
编程题、传教士人数M，野人C，M≥C，开始都在岸左边，
①船只能载两人，传教士和野人都会划船，当然必须有人划船
②两岸边保证野人人数不能大于传教士人数
把所有人都送过河，设计一方案，要求编程实现。
思路：
深度搜索。
状态：左岸和右岸的人数+船的位置。
每一个状态下，会有5种状态可以转移，
即：
1，运送2个传教士到对岸；
2，运送2个野人到对岸；
3，运送1个传教士到对岸；
4，运送1个野人到对岸；
5，运送1个传教士和一个野人到对岸。
从初始状态开始搜，搜索这五种情况，
进入下一状态，判断该状态是否满足条件，
即两岸野人的个数是否比该岸的传教士多，
如果满足条件，则继续搜索该状态下的五种情况。
深度搜索下去，直到找到最后的解。
注意：
1，如果搜索的状态在之前已经出现过了，就不深入下去了，
否则会出现死循环，比如运两个野人过去，再运回来，状态复原了，
如果一直这么搜下去，就没玩没了了。
2，状态包括船的信息，如果两边的人数都是一样，但是船的位置不一样，
那么这是两种状态。
3，要搜索的目标状态是人都在对岸且船在对岸。
PS：
当M=C>3时，没有解。
当M>C时，有解。
1 #include <iostream> 2 #include <vector> 3 #include <string> 4 #include <stdio.h> 5 using namespace std; 6 7 bool flag = true; //true:表示在右岸 8 vector<string> visit; //记录已经访问过的状态 9 10 bool dfs( int M, int C, int m, int c){ 11 if( M<0||C<0||m<0||c<0) //非法 12 return false; 13 if( (M&&C>M) ||(m&&c>m)) //野人会吃牧师 14 return false; 15 16 if( flag&&M==0&&C==0 ||(!flag&&m==0&&c==0)) //全部运输过去 17 return true; 18 19 //检查该节点是否出现过 20 char s[30]; 21 if( !flag ) 22 sprintf( s, "M=%d,C=%d,m=%d,c=%d,boat=left", M,C,m,c); 23 else 24 sprintf( s, "M=%d,C=%d,m=%d,c=%d,boat=right", m,c,M,C); 25 string str(s); 26 for( int i=0; i<visit.size(); i++) 27 if( visit[i]==str) //该状态已经搜索过了 28 return false; 29 30 visit.push_back(str); 31 flag = !flag; 32 if( dfs( m+2, c, M-2,C) ){ 33 printf("2,0\n"); 34 printf("%s\n",s); 35 return true; 36 } 37 else if( dfs( m, c+2, M, C-2) ){ 38 printf("0,2\n"); 39 printf("%s\n",s); 40 return true; 41 } 42 else if( dfs( m+1, c+1, M-1, C-1) ){ 43 printf("1,1\n"); 44 printf("%s\n",s); 45 return true; 46 } 47 else if( dfs( m+1, c, M-1, C)){ 48 printf("1,0\n"); 49 printf("%s\n",s); 50 return true; 51 } 52 else if( dfs( m, c+1, M, C-1)){ 53 printf("0,1\n"); 54 printf("%s\n",s); 55 return true; 56 } 57 flag = !flag; 58 visit.pop_back(); 59 return false; 60 } 61 62 int main(){ 63 char s[30]; 64 int M=6,C=6,m=0,c=0; 65 sprintf( s, "M=%d,C=%d,m=%d,c=%d,boat=left", M,C,m,c); 66 printf("%s\n",s); 67 if(!dfs(M,C,0,0)) 68 cout << "Can not find the solution."<<endl; 69 return 0; 70 }
