}
#include
#include
#include
#include
using namespace std;
bool flag = true; //true:表示在右岸
vector
bool dfs( int M, int C, int m, int c){
if( M<0||C<0||m<0||c<0) //非法
return false;
if( (M&&C>M) ||(m&&c>m)) //野人会吃牧师
return false;
if( flag&&M==0&&C==0 ||(!flag&&m==0&&c==0)) //全部运输过去
return true;
//检查该节点是否出现过
char s[30];
if( !flag )
sprintf( s, "M=%d,C=%d,m=%d,c=%d,boat=left", M,C,m,c);
else
sprintf( s, "M=%d,C=%d,m=%d,c=%d,boat=right", m,c,M,C);
string str(s);
for( int i=0; i
if( visit[i]==str) //该状态已经搜索过了
return false;
visit.push_back(str);
flag = !flag;
if( dfs( m+2, c, M-2,C) ){
printf("2,0\n");
printf("%s\n",s);
return true;
}
else if( dfs( m, c+2, M, C-2) ){
printf("0,2\n");
printf("%s\n",s);
return true;
}
else if( dfs( m+1, c+1, M-1, C-1) ){
printf("1,1\n");
printf("%s\n",s);
return true;
}
else if( dfs( m+1, c, M-1, C)){
printf("1,0\n");
printf("%s\n",s);
return true;
}
else if( dfs( m, c+1, M, C-1)){
printf("0,1\n");
printf("%s\n",s);
return true;
}
flag = !flag;
visit.pop_back();
return false;
}
int main(){
char s[30];
int M=6,C=6,m=0,c=0;
sprintf( s, "M=%d,C=%d,m=%d,c=%d,boat=left", M,C,m,c);
printf("%s\n",s);
if(!dfs(M,C,0,0))
cout << "Can not find the solution."<
return 0;
}