BFS实现狼羊白菜农夫过河问题

本文主要是介绍BFS实现狼羊白菜农夫过河问题，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

#include<iostream>
#include<ctime>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<set>
#include<memory.h>
#include<algorithm>
using namespace std;

typedef long long ll;
typedef int ElemType;

string w = "0000";	//人、狼、羊、白菜的初始状态
string state, tmpstate; 

int path[20];	//存路径 

//狼吃羊，羊吃白菜 
bool Judge(string t)
{
	if ((t[0] != t[1] && t[1] == t[2]) || (t[0] != t[2] && t[2] == t[3]))
		return false;
	return true;
}

//由二进制转化为十进制 
int bit(string s)
{
	return ((s[0]-'0')<<3) + ((s[1]-'0')<<2) + ((s[2]-'0')<<1) + (s[3]-'0');
}

void BFS()
{
	memset(path, -1, sizeof(path));
	queue<string> q;	//记录多重选择
	
	//加入初始状态 
	path[0] = 0;
	q.push(w);
	
	int now = 0, tmp = 0;	//当前状态、临时状态	
	
	while (!q.empty() && path[15] == -1)	//如果队列不为空或都没到对岸则继续搜索 
	{
		//出队当前状态 
		state = q.front();	 
		q.pop();
		
		now = bit(state);                              
		//人带其他行动 
		for (int i = 1; i <= 3; ++i)	//分别判断人能否带狼、羊、白菜过河 
		{
			tmpstate = state;
			if(state[0] == state[i])
			{
				(tmpstate[0] == '0') ? (tmpstate[0] = '1', tmpstate[i] = '1') : (tmpstate[0] = '0', tmpstate[i] = '0');
				tmp = bit(tmpstate);
				
				//如果合法且不重复 
				if (Judge(tmpstate) && path[tmp] == -1)
				{
					q.push(tmpstate);
					path[tmp] = now;
				} 
			}
			//人单独行动 
			tmpstate = state;
			tmpstate[0] = (tmpstate[0] == '0' ? '1' : '0');
			tmp = bit(tmpstate);
			if (Judge(tmpstate) && path[tmp] == -1)
			{
				q.push(tmpstate);
				path[tmp] = now;
			} 
		} 
	}
}
 
string BtoS(int t)
{
	string tmp = "";
	while(t)
	{
		tmp += t%2 + '0';
		t /= 2;
	}
	while(tmp.length() < 4)
		tmp += '0';
	return tmp;
}

void PrintPath()
{
	string o = "1111";
	for (int i = 15; i > 0; i = path[i])
	{
		string t = BtoS(path[i]);	//转换后：菜羊狼人 
		if(t[3] == '0' && t[0] == '0' && o[3] == '1' && o[0] == '1')
			cout << "人和菜过河" << endl;
		else
			if(t[3] == '1' && t[0] == '1' && o[3] == '0' && o[0] == '0')
				cout << "人和菜回来" << endl;
			else
				if(t[3] == '0' && t[1] == '0' && o[3] == '1' && o[1] == '1')
					cout << "人和羊过河" << endl;
				else
					if(t[3] == '1' && t[1] == '1' && o[3] == '0' && o[1] == '0')
						cout << "人和羊回来" << endl;
					else
						if(t[3] == '0' && t[2] == '0' && o[3] == '1' && o[2] == '1')
							cout << "人和狼过河" << endl;
						else
							if(t[3] == '1' && t[2] == '1' && o[3] == '0' && o[2] == '0')
								cout << "人和狼回来" << endl;
							else
								if(t[3] == '0' && o[3] == '1')
									cout << "人过河" << endl;
								else
									if(t[3] == '1' && o[3] == '0')
										cout << "人回来" << endl; 
		o = t;
	}
}

signed main()
{
	
	BFS();
	PrintPath();
	
	return 0;
} 
 

这篇关于BFS实现狼羊白菜农夫过河问题的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！