nongfu.cpp

农夫过河问题：关于数据结构问题中的基本问题

#include<iostream.h>
int farmer(int location)
{
	return(0!=(location & 0x08));
}
int wolf(int location)
{
	return(0!=(location & 0x04));
}
int cabbage(int location)
{
	return(0!=(location & 0x02));
}
int goat(int location)
{
	return(0!=(location & 0x01));
}//0表示在南岸，1表示在北岸
int safe(int location)//安全状况
{
	if(goat(location)==cabbage(location)&&goat(location)!=farmer(location))
		return(0);
	if(goat(location)==wolf(location)&& goat(location)!=farmer(location))
		return 0;
	return 1;
}
void main()
{
	int location[16];//存放下一个的状态
	int fangwen[16];//存放判断是否已被访问过该状态用1表示
	int i,y=-1;
	int x;//暂时存放从队中出来的状态
	int front,rear;
	int quelen[100];//存放队列
	front=-1;
	rear=0;
	for(i=0;i<16;i++)
	{location[i]=-1;fangwen[i]=0;}
	quelen[rear]=0x00;
	location[0]=0;
	front++;
	x=quelen[front];
	while(front<=rear||front==0)
	{
		if(safe(x)&&fangwen[x]==0)//如果x为安全状态，则将它接下来的状态放入队列
		{
			location[x]=y;
			if(!farmer(x))//如果此时农夫在南岸，则将去北岸
			{

				rear++;
				quelen[rear]=x+8;
				if(!wolf(x))
				{rear++;quelen[rear]=x+12;}
				if(!cabbage(x))
				{rear++;quelen[rear]=x+10;}
				if(!goat(x))
				{rear++;quelen[rear]=x+9;}
			}
			else
			{
				rear++;
				quelen[rear]=x-8;
				if(wolf(x))
				{rear++;quelen[rear]=x-12;}
				if(cabbage(x))
				{rear++;quelen[rear]=x-10;}
				if(goat(x))
				{rear++;quelen[rear]=x-9;}
			}
			y=x;
		}
		fangwen[x]=1;//已访问过该状态则置1
		front++;
		x=quelen[front];
	}
    i=15;
	
	while(i!=0)
	{
		cout<<i<<endl;
		i=location[i];
	}	
}