本文主要是介绍JD 1204：农夫、羊、菜和狼的故事，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
OJ题目：click here~~
#define vegetable_go 0
#define vegetable_come 1
#define sheep_go 2
#define sheep_come 3
#define wolf_go 4
#define wolf_come 5
#define nothing_go 6
#define nothing_come 7using namespace std ;
typedef long long LL ;
string ope[8] = {"vegetable_go" , "vegetable_come" ,"sheep_go" , "sheep_come" ,"wolf_go" , "wolf_come" , "nothing_go" ,"nothing_come" } ;void Print(vector<int> &g){for(int i = 0;i < g.size();i++)cout << ope[g[i]] << endl ;puts("succeed") ;puts("") ;
}bool IsValid(int state , int func){switch(func){case vegetable_go : return (state&1) == 0 && (state&8) == 0 ;case vegetable_come : return (state&1) == 1 && (state&8) == 8 ;case sheep_go : return (state&2) == 0 && (state&8) == 0 ;case sheep_come : return (state&2) == 2 && (state&8) == 8 ;case wolf_go : return (state&4) == 0 && (state&8) == 0 ;case wolf_come : return (state&4) == 4 && (state&8) == 8 ;case nothing_go : return (state&8) == 0 ;case nothing_come : return (state&8) == 8 ;}
}bool IsSafe(int state){int a1, a2 , a4 , a8 ;if(state&1) a1 = 1 ;else a1 = 0 ;if(state&2) a2 = 1 ;else a2 = 0 ;if(state&4) a4 = 1 ;else a4 = 0 ;if(state&8) a8 = 1 ;else a8 = 0 ;if(a1 == a2 && a8 != a1) return false ;if(a2 == a4 && a8 != a2) return false ; ;return true ;
}int gao(int last , int func){switch(func){case vegetable_go : return last|9 ;case vegetable_come : return last&6 ;case sheep_go : return last|10 ;case sheep_come : return last&5 ;case wolf_go : return last|12 ;case wolf_come : return last&3 ;case nothing_go : return last|8 ;case nothing_come : return last&7 ;}
}
bool NotYet(int state , vector<int> &g){return find(g.begin() , g.end(), state) == g.end() ;
}void process(vector<int> &g,vector<int> &op){int last = g.back() ;if(last == 15){Print(op) ;return ;}for(int i = 0;i < 8;i++){if(IsValid(last,i)) {int now = gao(last,i) ;if(!IsSafe(now)) continue ;if(!NotYet(now , g)) continue ;g.push_back(now) ;op.push_back(i) ;process(g , op) ;g.pop_back() ;op.pop_back() ;}}
}int main(){vector<int> g ;vector<int> op ;g.push_back(0) ; //初始状态0000(2)，表示农夫，狼，羊，蔬菜都在河岸左边//目标状态1111(2)，表示农夫，狼，羊，蔬菜都在河岸右边process(g , op) ;return 0 ;
}这篇关于JD 1204：农夫、羊、菜和狼的故事的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
