river.cpp

三个强盗和三个商人过河的算法

#include "River.h"
#include <iostream>
#include <cmath>

River::River(RNode* node)
{
	this->startNode = node;
}

void River::search() {
	RNode* tempNode;

	usedList.push_back(new RNode(startNode->getnodeState()));
	searchList.push_back(new RNode(startNode->getnodeState()));
	int val = 0;
	bool searchflag = true;;

	int swapState;

	while(searchflag) {
		tempNode = searchList[val];

		for(int i=0; i != 5; i++) {
			if(add(tempNode->move(i), tempNode)) {
				searchflag = false;
				break;
			}
		}

		val++;
	}

	cout << tempNode->getnodeState() << endl;
	while(tempNode->getfatherNode()) {
		tempNode = tempNode->getfatherNode();
		cout << tempNode->getnodeState() << endl;			
	}
}

bool River::isValid(int state) {
	if(getPos(state, 1) > 3 || getPos(state, 2) > 3 || getPos(state, 3) > 3 || getPos(state, 4) > 3) {
		return false;
	}

	if((getPos(state, 1) != 0 && getPos(state, 1) < getPos(state, 2)) || (getPos(state, 3) != 0 && getPos(state, 3) < getPos(state, 4))) {
		return false;
	}

	for(vector<RNode*>::iterator iter = usedList.begin(); iter != usedList.end(); ++iter)
		if((*iter)->getnodeState() == state)
			return false;
	return true;
}

bool River::add(int swapState, RNode* tempNode) {
	if(swapState == -33) {
		return true;
	} else if(isValid(swapState)) {
		usedList.push_back(new RNode(swapState, tempNode));
		searchList.push_back(new RNode(swapState, tempNode));
	}
	return false;
}

int River::getPos(int state, int pos) const {
	return (abs(state)/(int)pow(10.0, 4-pos))%10;
}