[编程题]农夫、羊、菜和狼的故事
- 热度指数：4155 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
- 算法知识视频讲解
有一个农夫带一只羊、一筐菜和一只狼过河。如果没有农夫看管，则狼要吃羊，羊要吃菜。但是船很小，只够农夫带一样东西过河。问农夫该如何解此难题？
输入描述:
题目没有任何输入。
输出描述:
题目可能有多种解决方法，请输出步骤最少的任意一种解决方法，
按顺序输出农夫想把羊、菜、狼全部运过河需要哪几个步骤。
如果需要将羊带过河去则输出一行“sheep_go”。
如果需要将羊带回来则输出一行“sheep_come”。
如果需要将菜带过河去则输出一行“vegetable_go”。
如果需要将菜带回来则输出一行“vegetable_come”。
如果需要将狼带过河去则输出一行“wolf_go”。
如果需要将狼带回来则输出一行“wolf_come”。
如果需要空手返回则输出一行“nothing_come”。
如果需要空手过河则输出一行“nothing_go”。
输出任意一种可行的最简方案后，请在最后输出一行“succeed”。
示例1
输入
无
输出
按题目要求进行输出即可。
//明显要用到回溯法
#include<stdio.h>
#include<string.h>
typedef struct record{
int type; //sheep|vegetable|wolf|nothing
int dir; //come|go
}Rec;
char state[5]; //代表🐏🐺菜人的状态
Rec list[20];
int count;
int Judge(int x,int direct){//其实可以用map来做，可以很方便的去重
if(strcmp(state,"0111")==0&&x!=3) //防止无限循环
return 0;
if(count!=0&&x==list[count-1].type)//防止无限循环，例如第一次把羊带过去第二次又带回来
return 0;
if(x==3)//nothing
{
if(state[0]==state[1]||state[0]==state[2])
return 0;
return 1;
}
if(state[x]!=state[3])//想要带的和农夫根本不在一边
return 0;
else {
char tmp[5];
strcpy(tmp,state);
tmp[x]='1'-tmp[x]+'0';
tmp[3]='1'-tmp[3]+'0';
if((tmp[0]==tmp[1]||tmp[0]==tmp[2])&&tmp[0]!=tmp[3])
return 0;
return 1;
}
}
void dfs(char * state,int direct){
if(strcmp(state,"1111")==0)
{
for(int i=0;i<count;i++){
switch(list[i].type){
case 0:printf("sheep_");break;
case 1:printf("wolf_");break;
case 2:printf("vegetable_");break;
case 3:printf("nothing_");break;
}
switch(list[i].dir){
case 0:printf("go\n");break;
case 1:printf("come\n");break;
}
}
printf("succeed\n");
return;
}
for(int i=3;i>=0;i--){//代表四个type，每次都从什么都不带开始遍历。
if(Judge(i,direct)){
char tmp = state[i];
list[count].type=i;//记录该操作
list[count].dir=direct;
count++;
state[i]=state[3]=1-direct+'0';//更改状态
dfs(state,1-direct);
state[i]=state[3]=tmp;//回溯
count--;
}
}
}
int main(){
strcpy(state,"0000");
count = 0;
dfs(state,0);
}
编辑于 2020-03-18 21:17:53
回复(1)
#include <stdio.h>
#include <stdlib.h>
//农夫过河问题，用1111的二进制分别代表河的一岸的农夫、狼、羊、菜，假如农夫带狼过河则1111变为0011
//总共有16种状态，每次过河的操作(8种操作)都会变成另外一个状态，直到得到0000，
//可以得到一个状态树，保存满足条件的路径
//不满足题目要求的状态有0111,0110,0011,1000,1001,1100
//建立一个当前搜索队列，保存遍历的状态，出现重复的状态则不进行这次变化（避免死循环），若队尾出现0，退出搜索
#define nothing_go -8
#define nothing_come 8
#define wolf_go -12
#define wolf_come 12
#define vegetable_go -9
#define vegetable_come 9
#define sheep_go -10
#define sheep_come 10
int Move[8] = {-12, -10, -9, -8, 8, 9, 10, 12};
typedef struct Results{
int r[100];
int length;
}Results;
Results Result[10];
int re_num=0;
int queue[100],length=0; //队列长度
int judge(int b, int m){//判断此次变化是否满足过河要求
int i, a = b + m;
if(m>0&&(m-8)&b>0)//如果是回来，那么你带的物品一定是这边没有的
//(m-8)&b==0表示带来的物品这边没有，防止羊被分解成菜带回来了
return 0;
if(m<0&&(abs(m)-8)&b==0)//带过去的物品一定要存在
return 0;
//判断过河后的状态是否满足条件或者出现过
if(a>15||a<0)
return 0;
if(a==12||a==9||a==8||a==7||a==6||a==3)
return 0;
for(i=0;i<length;i++)
if(a==queue[i])
return 0;
return 1;
}
//8种变化分别为
int Rivercross(int a){//生成状态树
int i;
queue[length]=a;
if(a==0){//过河成功，保存队列信息
for(i=0;i<length;i++){
Result[re_num].r[i]=queue[i];
}
Result[re_num].length=length+1;
re_num++;
return 1;
}
for(i = 0; i < 8; ++i) {
++length;
if(judge(a, Move[i]))
Rivercross(a + Move[i]);
--length;
}
}
void myprint(int index){//格式化输出
int i;
for(i=0;i<Result[index].length-1;i++){
switch(Result[index].r[i+1]-Result[index].r[i]){
case -8:printf("nothing_go\n");break;
case 8:printf("nothing_come\n");break;
case -12:printf("wolf_go\n");break;
case 12:printf("wolf_come\n");break;
case -9:printf("vegetable_go\n");break;
case 9:printf("vegetable_come\n");break;
case -10:printf("sheep_go\n");break;
case 10:printf("sheep_come\n");break;
}
}
}
int main()
{
int i,min_index=0;
Rivercross(15);
for(i=1;i<re_num;i++)//寻找最短路径序号
if(Result[i].length<Result[min_index].length)
min_index=i;
for(i=0;i<re_num;i++){//等于最短路径长度的结果输出
if(Result[i].length == Result[min_index].length){
myprint(i);
printf("succeed\n\n");
}
}
}
编辑于 2020-03-13 12:59:24
回复(6)
//最近刚学的算法，这属于用的回溯吗？ //感觉题目出的不严谨，因为最后输出的方案应该是有两个，第三步应该可以菜过河，也可以狼过河 //所以我的输出是两个，然而题目的答案只输出了一个😓😓😓。 #include<iostream> #include<vector> using namespace std; typedef struct Record{ int passage;//0 vegetables ; 1 sheep ; 2 wolf ;3 nothing int ifgo; //1 go ; 0 come Record(int a,int b):passage(a),ifgo(b){} }Record; vector<vector<Record> > result; //存储可行的乘船经历 vector<Record> rec; //记录当前状态 int goline[3]={1,1,1}; //等待过河的队伍的存在状态，1代表在，0代表不在（即在对面),3代表在渡船，下标0代表蔬菜，1代表羊，2代表狼 void goRiver(int lastPass); void comeRiver(int lastPass); bool ifFeasible(){ if(goline[2]==goline[1]||goline[1]==goline[0]) return false; return true; } bool ifEnd(){ for(int i=0;i<3;i++){ if(goline[i]!=0) return false; } return true; } void goRiver(int lastPass){ for(int i=0;i<3;i++){ if(goline[i]&&goline[i]!=lastPass){ goline[i]=3; if(ifFeasible()){ goline[i]=0; Record q(i,1); rec.push_back(q); comeRiver(i); goline[i]=1; rec.pop_back(); }else{ goline[i]=1; } } } return; } void comeRiver(int lastPass){ if(ifEnd()){ result.push_back(rec); return; } if(ifFeasible()){ Record q(3,0); rec.push_back(q); lastPass=3; goRiver(lastPass); } for(int i=0;i<3;i++){ if(goline[i]==0&&goline[i]!=lastPass){ goline[i]=3; if(ifFeasible()){ goline[i]=1; Record q(i,0); rec.push_back(q); goRiver(i); goline[i]=0; rec.pop_back(); }else{ goline[i]=0; } } } return; } int minRecord(){ int minnum=0; for(int i=0;i<result.size();i++){ if(result[i].size()<minnum) minnum=result[i].size(); } return minnum; } void printProcess(int n){ for(int i=0;i<result[n].size();i++){ string a,b; switch(result[n].at(i).passage){ case 0: a="vegetable_"; break; case 1: a="sheep_"; break; case 2: a="wolf_"; break; case 3: a="nothing_"; break; } switch(result[n].at(i).ifgo){ case 0: b="come"; break; case 1: b="go"; break; } cout<<a<<b<<endl; } } int main(){ goRiver(-1); int minnum=minRecord(); for(int i=0;i<result.size();i++){ if(result[i].si***num){ printProcess(i); cout<<"succeed"<<endl; } } }
发表于 2019-02-26 09:11:06
回复(2)
//1.农夫带🐏去
//2.农夫自己回
//3.农夫带菜去
//4.农夫带🐏回
//5.农夫带🐺去
//6.农夫空手回
//7.农夫带🐏去
#include<bits/stdc++.h>
using namespace std;
int main(){
printf("sheep_go\n");
printf("nothing_come\n");
printf("vegetable_go\n");
printf("sheep_come\n");
printf("wolf_go\n");
printf("nothing_come\n");
printf("sheep_go\n");
printf("succeed\n");
return 0;
}
//2.农夫自己回
//3.农夫带菜去
//4.农夫带🐏回
//5.农夫带🐺去
//6.农夫空手回
//7.农夫带🐏去
#include<bits/stdc++.h>
using namespace std;
int main(){
printf("sheep_go\n");
printf("nothing_come\n");
printf("vegetable_go\n");
printf("sheep_come\n");
printf("wolf_go\n");
printf("nothing_come\n");
printf("sheep_go\n");
printf("succeed\n");
return 0;
}
发表于 2020-01-20 15:39:11
回复(3)
#include<iostream>
#include <string>
#include <type_traits>
#include <vector>
#include <algorithm>
using namespace std;
bool danger(int& f, int& s, int& v, int& w);
bool visited(vector<string>& state, string s);
string build(int f, int s, int v, int w);
bool test(int& f, int& s, int& v, int& w, vector<string>& state);
bool cheak(int f, int s, int v, int w, vector<string>& state);
bool danger(int& f, int& s, int& v,
int& w) { //检测是否处于危险状态。
if ((s == v && f != s) || (w == s && f != w)) return true;
else return false;
}
bool visited(vector<string>& state,
string s) { //检测该状态是否已经访问过。
if (find(state.begin(), state.end(), s) != state.end()) {
return true;
} //访问过该状态则返回真
else {
state.push_back(
s); //未访问过时则将此状态记录，并访问该状态。
return false;
}
}
string build(int f, int s, int v,
int w) { //描述当前状态，生成状态字符串。
string temp;
temp.append(to_string(f));
temp.append(to_string(s));
temp.append(to_string(v));
temp.append(to_string(w));
return temp;
}
bool cheak(int f, int s, int v, int w,
vector<string>& state) { //根据当前环境与状态队列来判断当前状态是否访问过。
string str = build(f, s, v, w);
// for (auto it = state.begin(); it != state.end(); it++) cout << *it << ' ';
// cout << endl;
return visited(state, str);
}
bool test(int& f, int& s, int& v, int& w, vector<string>& state) {
if (f & s & v & w) {
cout << "succeed" <<
endl; //找到解时输出，并返回真值以结束查找。
return true;
} else {
if (f == 0) {
f = 1;
if (danger(f, s, v, w) || cheak(f, s, v, w, state)) {
f = 0; //新状态危险或已访问时，进行回溯。
} else {
cout << "nothing_go" << endl;
if (test(f, s, v, w, state)) return
true; //若找到解，则会逐层返回真值以退出递归。
f = 0; //上一条路径无法找到解时，同样进行回溯。
}
if (s == f) {
f = 1;
s = 1;
if (danger(f, s, v, w) || cheak(f, s, v, w, state)) {
f = 0;
s = 0;
} else {
cout << "sheep_go" << endl;
if (test(f, s, v, w, state)) return true;
f = 0;
s = 0;
}
}
if (v == f) {
f = 1;
v = 1;
if (danger(f, s, v, w) || cheak(f, s, v, w, state)) {
f = 0;
v = 0;
} else {
cout << "vegetable_go" << endl;
if (test(f, s, v, w, state)) return true;
f = 0;
v = 0;
}
}
if (w == f) {
f = 1;
w = 1;
if (danger(f, s, v, w) || cheak(f, s, v, w, state)) {
f = 0;
w = 0;
} else {
cout << "wolf_go" << endl;
if (test(f, s, v, w, state)) return true;
f = 0;
w = 0;
}
}
} else {
f = 0;
if (danger(f, s, v, w) || cheak(f, s, v, w, state)) {
f = 1;
} else {
cout << "nothing_come" << endl;
if (test(f, s, v, w, state)) return true;
f = 1;
}
if (s == f) {
f = 0;
s = 0;
if (danger(f, s, v, w) || cheak(f, s, v, w, state)) {
f = 1;
s = 1;
} else {
cout << "sheep_come" << endl;
if (test(f, s, v, w, state)) return true;
f = 1;
s = 1;
}
}
if (v == f) {
f = 0;
v = 0;
if (danger(f, s, v, w) || cheak(f, s, v, w, state)) {
f = 1;
v = 1;
} else {
cout << "vegetable_come" << endl;
if (test(f, s, v, w, state)) return true;
f = 1;
v = 1;
}
}
if (w == f) {
f = 0;
w = 0;
if (danger(f, s, v, w) || cheak(f, s, v, w, state)) {
f = 1;
w = 1;
} else {
cout << "wolf_come" << endl;
if (test(f, s, v, w, state)) return true;
f = 1;
w = 1;
}
}
}
return false; //未找到解时返回假值以进行回溯。
}
}
int main() {
int farm = 0, sheep = 0, veg = 0, wolf = 0;
vector<string> state;
string s;
s = build(farm, sheep, veg, wolf); // 初始化状态队列。
state.push_back(s);
test(farm, sheep, veg, wolf, state);
return 0;
}
发表于 2023-03-22 02:15:34
回复(0)
#include <iostream>
#include <stdio.h>
using namespace std;
/*
用8位bit来表示两岸的状态，假设是从右岸到左岸， 右岸和左岸分别有四个状态，即 菜，羊，狼，农夫， 1表示在此岸，0表示不在此岸
初始时，为 0b0000 1111， 表示 菜，羊，狼，农夫全部在右岸。 有两岸，4种move，总共8种，如0b00000011,表示狼和农夫一起从右岸走， 0b00110000,表示狼和农夫一起从左岸走。
1.判断是否全到左岸，是则退出递归并输出相应的move。否，从四种move中选择一种，进入2
2.判断此岸是否有条件进行move，如此岸有狼才能wolf_go或wolf_come。若是，进入3，否，返回1
3.判断move与上次move是否对应，如 上次nothing_go,此次不能再次nothing_come。 若是，返回1，若否，进入4
4.渡河，两岸的状态改变，判断 离开的那一岸，是否会出现狼吃羊，羊吃菜的现象，若是，返回1，若否，进入5
5.更新两岸状态，回到1继续判断
中间遇到一个bug，也就是move_flag的顺序改变，第一个不是nothing_come和nothing_go，会陷入无限循环：
sheep_go, nothing_come, wolf_go, sheep_come, vegetable_go。 此时羊在右岸，农夫，狼和菜在左岸。
如果下一步选择 wolf_come, 那么就会出现死循环，而nothing_come则就能正确得出解。
改变move_flag内的顺序，就会出现bug
u8 move_flag[2][4] = { {WOLF_GO, SHEEP_GO, VEGETABLE_GO, NOTHING_GO},
{WOLF_COME, SHEEP_COME, VEGETABLE_COME, NOTHING_COME}};
将nothing_go,nothing_come放在第一个位置，隐含左岸优先级比右岸高，否则会出现两岸是等同地位，跳不出循环
*/
#define WOLF_EAT_SHEEP_RIGHT 0x06 // 农夫离开右岸，出现狼吃羊
#define WOLF_EAT_SHEEP_LEFT 0x60 // 左岸，狼吃羊
#define SHEEP_EAT_VEG_RIGHT 0x0c // 右岸，羊吃菜
#define SHEEP_EAT_VEG_LEFT 0xc0 // 左岸，羊吃菜
#define RIGHT 0
#define LEFT 1
#define MAX_SIZE 300
#define NOTHING_GO 0b00000001
#define NOTHING_COME 0b00010000
#define WOLF_GO 0b00000011
#define WOLF_COME 0b00110000
#define SHEEP_GO 0b00000101
#define SHEEP_COME 0b01010000
#define VEGETABLE_GO 0b00001001
#define VEGETABLE_COME 0b10010000
typedef unsigned char u8;
string a[MAX_SIZE];
u8 move_flag[2][4] = { {NOTHING_GO, WOLF_GO, SHEEP_GO, VEGETABLE_GO},
{NOTHING_COME, WOLF_COME, SHEEP_COME, VEGETABLE_COME}};
void init() {
a[NOTHING_GO] = "nothing_go";
a[WOLF_GO] = "wolf_go";
a[SHEEP_GO] = "sheep_go";
a[VEGETABLE_GO] = "vegetable_go";
a[NOTHING_COME] = "nothing_come";
a[WOLF_COME] = "wolf_come";
a[SHEEP_COME] = "sheep_come";
a[VEGETABLE_COME] = "vegetable_come";
}
void cross_river(u8 river_flag, bool &zflag, u8 last_move) {
if ( river_flag == 0b11110000) { // 都到左岸，退出递归
zflag = true;
return ;
}
int this_side = (river_flag & 0x01) == 0x01 ? RIGHT : LEFT;
int that_side = (river_flag & 0x01) == 0x01 ? LEFT : RIGHT;
for (int i = 0; i < 4; i++) {
if ((move_flag[this_side][i] & river_flag) != move_flag[this_side][i] ) { // 判断this_side有对应的事物才能带到对面去，也就能执行相应的move
continue;
}
if (last_move == move_flag[that_side][i]) { // 上一次和此次的move应该不一致，否则此次move是无意义的
continue;
}
u8 rf_temp = river_flag - move_flag[this_side][i] | move_flag[that_side][i]; // 渡河，到达了对岸，此时两岸的状态
// 离开了右岸，判断右岸是否出现了狼吃羊，或羊吃菜的现象
if (this_side == RIGHT && ((rf_temp & WOLF_EAT_SHEEP_RIGHT) == WOLF_EAT_SHEEP_RIGHT || (rf_temp & SHEEP_EAT_VEG_RIGHT) == SHEEP_EAT_VEG_RIGHT)) {
continue;
}
// 离开了左岸，判断左岸是否出现了狼吃羊，或羊吃菜的现象
if (this_side == LEFT && ((rf_temp & WOLF_EAT_SHEEP_LEFT) == WOLF_EAT_SHEEP_LEFT || (rf_temp & SHEEP_EAT_VEG_LEFT) == SHEEP_EAT_VEG_LEFT) ) {
continue;
}
// 上述条件都通过，此次move有意义，进入下一次抉择
cross_river(rf_temp, zflag, move_flag[this_side][i]);
if (zflag) {
cout << a[move_flag[this_side][i]] << endl;
return;
}
}
}
int main() {
u8 river_flag = 0x0f; // 0b 0000 1111, 低四位是右边的河岸，从右到左，1表示 农夫，狼，羊，菜
bool zflag = false;
init();
cross_river(river_flag, zflag, 0x00);
if (zflag) {
cout << "succeed" << endl;
}
return 0;
}
// 64 位输出请用 printf("%lld")
发表于 2023-03-03 09:16:55
回复(0)
//羊go 无come 菜go 羊come 狼go 无come 羊go,前提条件羊必须自己在一边
#include<stdio.h>
int main()
{
printf("sheep_go\n");
printf("nothing_come\n");
printf("vegetable_go\n");
printf("sheep_come\n");
printf("wolf_go\n");
printf("nothing_come\n");
printf("sheep_go\n");
printf("succeed\n");
}
发表于 2020-03-30 21:49:07
回复(0)
广度优先搜索，在求最终的路径时感觉绕弯有点多，求指点😊
#include <stdio.h>
#include <queue>
using namespace std;
queue<int> S;
int visit[20];//用来保存当前状态的前一状态
int a[4]={8,12,10,9};//用来表示4种状态转换操作
bool judge(int x)
{//用来判断是否为合法状态
if(x>=5&&x<=10)
return false;
else if(x>15 || x<0)
return false;
else if(visit[x]!=-1)
return false;
else
return true;
}
void BFS()
{
int current=S.front();
S.pop();
for(int i=0;i<4;i++ )
{
int next=a[i]^current;
if(judge(next))
{
S.push(next);
visit[next]=current;
if(next == 15)
return;
}
}
BFS();
}
void myprint(int a1,int a2)
{
switch(a2-a1)
{
case -8: printf("nothing_come\n");break;
case -12: printf("sheep_come\n");break;
case -10: printf("vegetable_come\n");break;
case -9: printf("wolf_come\n");break;
case 8: printf("nothing_go\n");break;
case 12: printf("sheep_go\n");break;
case 10: printf("vegetable_go\n");break;
case 9: printf("wolf_go\n");break;
}
}
int main()
{
int state =0;
for(int i=0;i<16;i++)
visit[i]=-1;
S.push(state);
visit[state]=-2;
BFS();
int x=15;
int a[20];//根据visit数组来获得路径顺序，即状态序列
int idx=0;
while(x!=-2)
{
a[idx++]=x;
x=visit[x];
}
for(int i=idx-1;i>0;i--)
{//根据a数组即状态序列的变换打印状态转换过程
myprint(a[i],a[i-1]);
}
printf("succeed\n");
return 0;
}
编辑于 2019-07-28 15:27:57
回复(0)
羊过去空手回来此时既可以让狼过去也可以让菜过去
之后带羊回 把不是羊的那个带过去 空手回 最后带羊过去
应该有两种方案才对啊
发表于 2019-03-17 01:19:58
回复(0)
宽度优先遍历
#include <iostream>
#include <vector>
#include <queue>
#include <map>
using namespace std;
bool is_visited[2][2][2][2] = { false };
struct State{
int person;
int wolf;
int sheep;
int vegetable;
int path; //记录之前的操作序列，每一位代表一个操作
State(int p,int w,int s,int v, int way):person(p),wolf(w),sheep(s),vegetable(v),path(way){}
};
//(人，狼，羊，菜)四元组，0表示在此岸，1表示在对岸
bool is_valid(int p, int w, int s, int v){
if(w == s && p != w)
return false;
if(s == v && p != s)
return false;
if(p < 0 || w < 0 || s < 0 || v < 0)
return false;
if(p > 1 || w > 1 || s > 1 || v > 1)
return false;
if(p == 0 && w == 0 && s == 0 && v == 0)
return false;
return !is_visited[p][w][s][v];
}
bool operation(int op, State &s){
int np = s.person, nw = s.wolf, ns = s.sheep, nv = s.vegetable;
switch (op){
case 1:
np++;
ns++;
break;
case 2:
np--;
ns--;
break;
case 3:
np++;
nv++;
break;
case 4:
np--;
nv--;
break;
case 5:
np++;
nw++;
break;
case 6:
np--;
nw--;
break;
case 7:
np++;
break;
case 8:
np--;
break;
}
if(is_valid(np, nw, ns, nv)){
s.person = np, s.wolf = nw, s.sheep = ns, s.vegetable = nv;
s.path = s.path * 10 + op;
return true;
}
else
return false;
}
void display(int path){ //输出转移方法
string str = to_string(path);
while(str.size() != 0){
switch (str[0] - '0'){
case 1:
cout<<"sheep_go"<<endl;
break;
case 2:
cout<<"sheep_come"<<endl;
break;
case 3:
cout<<"vegetable_go"<<endl;
break;
case 4:
cout<<"vegetable_come"<<endl;
break;
case 5:
cout<<"wolf_go"<<endl;
break;
case 6:
cout<<"wolf_come"<<endl;
break;
case 7:
cout<<"nothing_go"<<endl;
break;
case 8:
cout<<"nothing_come"<<endl;
break;
}
str.erase(str.begin());
}
}
void bfs(State s){
queue<State> myqueue;
myqueue.push(s);
while(!myqueue.empty()){
State temp = myqueue.front();
myqueue.pop();
if(temp.person == 1 && temp.wolf == 1 && temp.sheep == 1 && temp.vegetable == 1){
display(temp.path);
cout<<"succeed"<<endl;
return ;
}
for(int i = 1; i <= 8; i++){
bool flag = operation(i, temp);
if(flag){
is_visited[temp.person][temp.wolf][temp.sheep][temp.vegetable] = true;
myqueue.push(temp);
}
}
}
}
int main() {
State start(0, 0, 0, 0, 0);
bfs(start);
}
发表于 2024-03-06 17:09:40
回复(0)
最少的步骤，故采用 BFS
(1)状态空间：(标记数组 flags, 当前步骤 step, 过河过程 process)
(2)状态转移：flags 中和农夫在一起的可以随农夫过河(或者什么都不带)，step + 1， process += i(0, 1, 2, 3)
(3)起始状态：({X, 0, 0, 0}, 0, "")
(4)目标状态：({X, 1, 1, 1, Odd, "xxxxxxx"}
搜索树：
({0,0,0}, 0, "")
/
({0,1,0}, 1, "1")
/ \
({0,1,0}, 2, "10") ({0,0,0}, 2, "11") ......
#include <iostream>
#include <string>
#include <queue>
using namespace std;
string map[4] = {"nothing", "vegetable", "sheep", "wolf"};
struct Status {
bool flags[4]; // 下标 1, 2, 3 分别表示蔬菜，羊，狼，下标 0 冗余；false 表示在河这岸，true 表示过河对岸
int step; // 表当前第几步，为偶数时农夫在河这岸，为奇数时农夫过河对岸
string process; // 过河步骤过程
Status(bool f[3], int s, string p) {
flags[0] = false;
for (int i = 1; i <= 3; i++) {
flags[i] = f[i - 1];
}
step = s;
process = p;
}
};
bool Valid(const Status& s) {
bool f = s.step % 2 == 0; // 偶数时农夫在河这岸，就检查河对岸；反之亦然
// if (s.flags[1] == f && s.flags[2] == f) { // 蔬菜和羊在一起
// return false;
// }
// if (s.flags[2] == f && s.flags[3] == f) { // 羊和狼在一起
// return false;
// }
// return true;
return !(s.flags[1] == f && s.flags[2] == f || s.flags[2] == f && s.flags[3] == f);
}
bool Succeed(const Status& s) {
return s.flags[1] && s.flags[2] && s.flags[3]; // 蔬菜，羊和狼都到达河对岸
}
string BFS() {
queue<Status> q;
bool initFlags[3] = {false, false, false};
q.push(Status(initFlags, 0, "")); // 压入初始状态
while (!q.empty()) {
Status cur = q.front();
q.pop();
if (Succeed(cur)) { // 找到了目标状态
return cur.process;
}
for (int i = 0; i <= 3; i++) {
Status next = cur; // 每轮循环都创建一个新的 next，避免各个 next 数据互相影响
next.step ++;
next.process += (i + '0'); // 当前步骤带什么过河，0 表示什么都不带
bool flag = next.step % 2 == 1;
if (i != 0 && !next.flags[i] == flag) { // 如果当前步骤农夫要过河对岸，则只能带目前在河这岸的；反之亦然
next.flags[i] = flag;
}
if (Valid(next)) {
q.push(next);
}
}
}
}
void PrintProcess(string process) {
for (int i = 0; i < process.size(); i++) {
if (i % 2) {
cout << map[process[i] - '0'] << "_come" << endl;
} else {
cout << map[process[i] - '0'] << "_go" << endl;
}
}
cout << "succeed" << endl;
}
int main() {
string process = BFS();
PrintProcess(process);
return 0;
}
发表于 2022-05-01 22:55:07
回复(0)
//不会回溯。。。自己写了个逻辑调好半天。。。
#include <iostream>
#include <string.h>
using namespace std;
void goahead();
void print(int a[],int n);
const int maxin=10;
int arr[2][3];
int step[maxin];
int final_step[maxin];
int len=0,num=0;
int cnt=-1;
bool judge_OK(int a[])
{
if(a[0]&&a[1])
return false;
else if(a[1]&&a[2])
return false;
else return true;
}
void goback()
{
if(arr[1][0]&&arr[1][1]&&arr[1][2])
{
if(!num||num>len)
{
num=len;
for(int i=0;i<num;i++)
final_step[i]=step[i];
}
return;
}
int pre=cnt;
for(int i=0;i<4;i++)
{
if(arr[1][0]&&arr[1][2]) i=3;
if(i!=cnt&&arr[1][i]&&i!=3)
{
arr[1][i]=0;
if(!judge_OK(arr[1])) arr[1][i]=1;
else
{
arr[0][i]=1;
cnt=i;
step[len++]=i;
goahead();
len--;
cnt=pre;
arr[0][i]=0;
arr[1][i]=1;
}
}
else if(i==3)
{
if(!judge_OK(arr[1])) break;
else{
cnt=-1;
step[len++]=i;
goahead();
len--;
cnt=pre;
}
}
}
}
void goahead()
{
for(int i=0;i<4;i++)
{
int pre=cnt;
if(i!=cnt&&i!=3&&arr[0][i])
{
arr[0][i]=0;
if(!judge_OK(arr[0])) arr[0][i]=1;
else
{
arr[1][i]=1;
cnt=i;
step[len++]=i;
goback();
len--;
cnt=pre;
arr[1][i]=0;
arr[0][i]=1;
}
}
else if(i==3&&!arr[0][0]&&!arr[0][1]&&!arr[0][2])
{
if(!judge_OK(arr[0])) break;
else{
cnt=-1;
step[len++]=i;
goback();
len--;
cnt=pre;
}
}
}
}
void print(int a[],int n)
{
for(int i=0;i<n;i++)
{
if(i%2)
{
switch(a[i])
{
case 0:cout<<"wolf_come"<<endl;
break;
case 1:cout<<"sheep_come"<<endl;
break;
case 2:cout<<"vegetable_come"<<endl;
break;
case 3:cout<<"nothing_come"<<endl;
break;
default:break;
}
}
else
{
switch(a[i])
{
case 0:cout<<"wolf_go"<<endl;
break;
case 1:cout<<"sheep_go"<<endl;
break;
case 2:cout<<"vegetable_go"<<endl;
break;
case 3:cout<<"nothing_go"<<endl;
break;
default:break;
}
}
}
cout<<"succeed"<<endl;
}
int main()
{
for(int i=0;i<3;i++)
{
arr[0][i]=1; //0表示狼，1表示羊，2表示菜,3表示空手；
arr[1][i]=0;
}
goahead();
print(final_step,num);
}
发表于 2022-02-19 19:19:40
回复(0)
#include <iostream>
#include <vector>
#include <string>
#define GAME_WIN 1
#define GAME_OVER -1
#define GAME_NORMAL 0
#define DIR_GO 0
#define DIR_COME 1
typedef union{
uint8_t data;
struct{
uint8_t sheep:1;
uint8_t vegetable:1;
uint8_t wolf:1;
uint8_t farmer:1;
}all;
}Game;
typedef struct{
uint8_t data;
int dir;
int status;
std::string detail;
}Step;
int check(Game &g) {
switch(g.data) {
case 0b0000:
return GAME_WIN;
case 0b0111:
case 0b0101:
case 0b0011:
case 0b1000:
case 0b1010:
case 0b1100:
return GAME_OVER;
default:
return GAME_NORMAL;
}
}
int move_sheep(Game &g) {
if(g.all.farmer == g.all.sheep) {
g.data ^= 0b1001;
return g.all.farmer; // 0 = go, 1 = come
}
return GAME_OVER; // bad move = game over
}
int move_vegetable(Game &g) {
if(g.all.farmer == g.all.vegetable) {
g.data ^= 0b1010;
return g.all.farmer;
}
return GAME_OVER;
}
int move_wolf(Game &g) {
if(g.all.farmer == g.all.wolf) {
g.data ^= 0b1100;
return g.all.farmer;
}
return GAME_OVER;
}
int move_farmer(Game &g) {
g.data ^= 0b1000;
return g.all.farmer; // 0 = go, 1 = come
}
int next_move(Game &g, int type) {
switch(type) {
case 0:
return move_sheep(g);
case 1:
return move_vegetable(g);
case 2:
return move_wolf(g);
case 3:
return move_farmer(g);
default:
return GAME_OVER;
}
}
std::vector<Step> history;
int dir = 0, status = 0;
void dfs(Game &g) {
// game over -> return
if(dir == GAME_OVER || status == GAME_OVER) {
return;
}
// win -> return
if(status == GAME_WIN) {
for(int i = 1; i < history.size(); ++i) { // skip the initial state
std::cout << history[i].detail << std::endl;
}
std::cout << "succeed" << std::endl;
return;
}
// check loop -> return
for(int i = 0; i < history.size() - 1; ++i) {
if(history[i].data == g.data)
return;
}
for(int i = 0; i < 4; ++i) {
// move and check
dir = next_move(g, i);
status = check(g);
// save history
Step s;
s.data = g.data;
s.dir = dir;
s.status = status;
switch(i) {
case 0:
s.detail = "sheep_";
break;
case 1:
s.detail = "vegetable_";
break;
case 2:
s.detail = "wolf_";
break;
case 3:
s.detail = "nothing_";
break;
default:
break;
}
s.detail.append(s.dir == DIR_GO ? "go" : "come");
history.push_back(s);
// next step
dfs(g);
// backtrack
history.pop_back();
g.data = history.back().data;
dir = history.back().dir;
status = history.back().status;
}
}
int main() {
Game game;
game.data = 0x0F; // game init
Step s;
s.data=0x0f;
history.push_back(s); // history init
dfs(game);
return 0;
}
发表于 2022-01-25 01:51:25
回复(0)
import java.util.*;
/**0：农夫， 1：羊， 2：菜， 3：狼*/
public class Main{
private static int[] status = {0, 0, 0, 0};
private static boolean flag;
private static Stack<String> q = new Stack<>();
private static HashMap<String, Boolean> isExist = new HashMap<>();
private static String[] info = {"nothing_", "sheep_", "vegetable_", "wolf_"};
private static String[] way = {"come", "go"};
public static String state(){
StringBuilder sb = new StringBuilder();
for(int i = 0; i < 4; i++)
sb.append(status[i]);
return new String(sb);
}
public static boolean Judge(){
if(status[1] == status[2] && status[1] != status[0])
return false;
if(status[1] == status[3] && status[1] != status[0])
return false;
return true;
}
public static void dfs(int x){
if(status[0] == 1 && status[1] == 1 && status[2] == 1 && status[3] == 1){
flag = true;
for(String str : q)
System.out.println(str);
System.out.println("succeed");
return;
}
for(int i = 0; i < 4; i++){
if(status[i] == x)
continue;
status[i] = x;
status[0] = x;
String curState = state();
if(isExist.containsKey(curState)){
status[i] = 1 - x;
status[0] = 1 - x;
continue;
}
if(Judge()){
q.add(info[i] + way[x]);
isExist.put(curState, true);
dfs(1 - x);
if(flag)
return;
q.pop();
}
else{
status[i] = 1 - x;
status[0] = 1 - x;
}
}
}
public static void main(String[] args){
dfs(1);
}
}
发表于 2021-06-16 20:58:02
回复(0)
#include<stdio.h>
void Print(int x){
switch(x){
case 1: printf("sheep_go\n");break;
case 2: printf("sheep_come\n");break;
case 3: printf("vegetable_go\n");break;
case 4: printf("vegetable_come\n");break;
case 5: printf("wolf_go\n");break;
case 6: printf("wolf_come\n");break;
case 7: printf("nothing_go\n");break;
case 8: printf("nothing_come\n");break;
case 9: printf("succeed\n");break;
default:printf("Error!\n");
}
}
int main(){
Print(1);//农夫带羊过河
Print(8);//农夫自己回去
Print(3);//农夫带菜过河
Print(2);//农夫带羊回去
Print(5);//农夫带狼过河
Print(8);//农夫自己回去
Print(1);//农夫带羊过河
Print(9);//成功
}
发表于 2021-02-26 16:01:00
回复(0)
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
