farmerproblem.cpp

农夫过河的扩展

#include<iostream.h>
#include"SeqQueue.h"
#include"safe.cpp"

void main(){
	int mover1,mover2,location,newlocation;
	int route[64];
	for (int i=0;i<64;i++)
		route[i] = -1;
	SeqQueue move;
	move.enQueue(0x00);
	route[0] = 0;
	while(!move.isEmptyQueue()&&route[63]==-1){
		location = move.frontQueue();
		move.deQueue();
		for(mover1=1;mover1<=32;mover1<<=1){
				if ((0!=(location&0x20))==(0!=(location&mover1)))
				{
					newlocation = location^(0x20|mover1);
					if (isSafe(newlocation)&&route[newlocation]==-1){
						route[newlocation] = location;
						move.enQueue(newlocation);
					}
				}
			}
		/////////////////////////////////////////////////////
		//location = move.frontQueue();
		//move.deQueue();
		for(mover1=1;mover1<=16;mover1<<=1)
			for(mover2=mover1,mover2<<=1;mover2<=32;mover2<<=1){
				if ((0!=(location&0x20))==(0!=(location&mover1))&&
					(0!=(location&0x20))==(0!=(location&mover2)))
				{
					newlocation = location^(0x20|mover1|mover2);
					if (isSafe(newlocation)&&route[newlocation]==-1){
						route[newlocation] = location;
						move.enQueue(newlocation);
					}
				}
			}
	}
	if (route[63]!=-1){
		cout<<"The probable path:\n";
		for (location=63;location>=0;location=route[location]){
			cout<<"position:"<<location<<endl;
			if (location==0) return;
		}
	}
	else
		cout<<"No solution!!\n";
}