#include"cqueueVector.h"
#include"vector.h"
#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);
}

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 farmerProblem()
{
	queueVector<int>moveTo(16);
	vector<int>route(16,-1);
	moveTo.enqueue(0x00);
	route[0]=0;
	int location;
	while(!moveTo.isEmpty()&&(route[15]==-1))
	{
		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 solution!";
}
void main()
{
  farmerProblem();
}