farmerproblem.cpp

vc当中比较容易遇到的过河问题

#include"link.h"
#include"clist.h"
#include"queueList.h"
#include"vector.h"
#include<iostream.h>
using namespace std;

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);
}

int safe(int location)
{
if((goat(location)==cabbage(location)) && 
   (goat(location)!=farmer(location)))
return 0;
return 1;
}

void farmerProblem()
{
	queueList<int>moveTo(16);
	vector<int>route(16,-1);
	moveTo.enqueue(0x00);
	route[0]=0;
	while(!moveTo.isEmpty() && (route[15]==-1)){
		int location=moveTo.dequeue();
		for(int movers=1;movers<=8;movers<<=-1)
		{
			if((0!=location & 0x08)==(0!=location & movers))
			{
				int newLocation=location^(0x08|movers);
				if(safe(newLocation)&&
					(route[newLocation]=-1)){
					route[newLocation]=location;
					moveTo.enqueue(newLocation);
				}
			}
		}
}

if(route[15]!=-1)
{
cout<<"path:";
for(int location=15;location>=0;
    location=route[location])
cout<<location<<',';
cout<<0<<'\n';
}
else cout<<"No silution!";
}

void main
{
farmerProblem();
}