题解 | 农夫、羊、菜和狼的故事

#include<iostream>
#include<string>
#include<vector>
using namespace std;

//搜索（物品，是否已经移动到对岸了,动作，搜索结果,是否在对岸,上一轮带的谁,原则上不带回）
int search_by_backTracking(string item[],int location[],string action[],vector<string>& vect,int k,int p){
	//选中这一轮携带的物品
	if(k==0){	//农夫在出发的一侧
		for(int i = 0;i< item->length()-1;i++){
			if(location[i]==1&&i!=p){	//说明可以携带
				location[i] = -1;
				//如果羊和菜呆在一起，显然是不可行的，如果羊和狼呆在一起，显然也不可行
				if(location[0]==location[1]&&location[0]==1&&location[1]==1||location[0]==location[2]&&location[0]==1&&location[2]==1){
					location[i] = 1;
				}else{//如果暂时是可行的，那么我们就按照这个方法做
					p = i;
					vect.push_back(item[i] + action[1]);
					//检查当前是否所有的东西都已经运抵到对岸了
					bool flag = false;
					for(int i = 0;i<item->length()-1;i++){
						if(location[i]==1){
							flag = true;
							break;
						}
					}
					//这一趟过去已经运输完成了，输出结果就行
					if(!flag){
						for(int i = 0;i<vect.size();i++){
							cout<<vect[i]<<endl;
						}
						return 1;
					}else{
						//搜索失败，及时回退
						if(search_by_backTracking(item,location,action,vect,(k+1)%2,p)==-1){
							vect.pop_back();
							location[i] = 1;
						}else{
							return 1;
						}
					}
				}
			}
		}
	}else{		//农夫在返回的那一侧
		for(int i = item->length()-1;i>=0;i--){
			if(i!=p&&location[i]==-1||location[i]==2){	//说明可以携带物品返回,如果留在河岸没有冲突，我们就没有必要把东西带回
				if(i<3) location[i] = 1;
				//如果羊和菜呆在一起，显然是不可行的，如果羊和狼呆在一起，显然也不可行
				if(location[0]==location[1]&&location[0]==-1&&location[1]==-1||location[0]==location[2]&&location[0]==-1&&location[2]==-1){
					location[i] = -1;
				}else{//如果暂时是可行的，那么我们就先按照这个做
					p = i;
				      	vect.push_back(item[i] + action[0]);
				      	if(search_by_backTracking(item,location,action,vect,(k+1)%2,p)==-1){
						vect.pop_back();
						if(i<3) location[i] = -1;
					}else{
						return 1;
					}
				}
			}
		}
	}
	return -1;
}

/*
 *农夫,羊,菜和狼的故事
 * */
int main(){
	string item[] = {"sheep","vegetable","wolf","nothing"};
	int location[] = {1,1,1,2};
	string action[] = {"_come","_go"};	//返回，过河
	vector<string> vect;	//放置搜索到的结果
	if(search_by_backTracking(item,location,action,vect,0,-1)==1){
		cout<<"succeed"<<endl;
		return 0;
	}
}