这个月没写几篇东西，唉，各种事情，鉴于人工智能课程，也是N就A*的概念有了，却没写过几个题目，这里就做了这个8数码问题了，不过，真的写得太长，太冗余了。

#include <cstdio>
#include <queue>
#include <map>
#include <vector>
using namespace std;

int abs(int x){
	if(x<0)return -x;
	return x;
}

class Eight{
private:
	static const char goalStatus[3][3];
	static const char goalPosition[9][2];
	char matrix[3][3],distance,x0,y0;
	int step;
	char method;
public:
	Eight();
	char getDistance();
	void print()const;
	bool operator ==(Eight&)const;
	Eight& operator = (Eight);
	Eight& operator = (const char mx[3][3]);
	bool moveUp();
	bool moveRight();
	bool moveDown();
	bool moveLeft();
	vector<Eight> getNextStatus()const;
	int getValue()const;
	int getStep()const;
	void setStep(int);
};

const char Eight::goalStatus[3][3]={
	{1,2,3},
	{4,5,6},
	{7,8,0}
};

const char Eight::goalPosition[9][2]={
	{2,2},//0
	{0,0},//1
	{0,1},//2
	{0,2},//3
	{1,0},//4
	{1,1},//5
	{1,2},//6
	{2,0},//7
	{2,1} //8
};

Eight::Eight(){
//	printf("0x%X\n",this);
	distance=-1;
	step=0;
}

char Eight::getDistance(){
	if(distance==-1){
		distance=0;
		for(int i=0;i<3;i++){
			for(int j=0;j<3;j++){
				if(matrix[i][j]==0)continue;/*8 6 7 2 5 4 3 x 1 巨大差异*/
				/*直接判断不在目的位置的数量做
				if(matrix[i][j]!=goalStatus[i][j])
					distance++;*/
				/*判断相对距离做*/
				distance+=
					abs(goalPosition[matrix[i][j]][0]-i)
				+	abs(goalPosition[matrix[i][j]][1]-j);
			}
		}
	}
	return distance;
}

void Eight::print()const{
//	printf("#%d %d\n",distance+step,getValue());
	putchar(method);
/*	for(int i=0;i<3;i++){
		for(int j=0;j<3;j++){
			printf("%3d",matrix[i][j]);
		}
		puts("");
	}
	puts("");*/
}

Eight& Eight::operator = (const char mx[3][3]){
	for(int i=0;i<3;i++){
		for(int j=0;j<3;j++){
			matrix[i][j]=mx[i][j];
			if(matrix[i][j]==0){
				y0=i;
				x0=j;
			}
		}
	}
	distance=-1;
	getDistance();
	step=0;
	return *this;
}

Eight& Eight::operator = (Eight b){
	for(int i=0;i<3;i++){
		for(int j=0;j<3;j++){
			matrix[i][j]=b.matrix[i][j];
		}
	}
	distance=b.distance;
	x0=b.x0;
	y0=b.y0;
	step=b.step;
	method=b.method;
	return *this;
}

//0的移动方向
bool Eight::moveUp(){
	if(y0<1)return false;
	matrix[y0][x0]^=matrix[y0-1][x0];
	matrix[y0-1][x0]^=matrix[y0][x0];
	matrix[y0][x0]^=matrix[y0-1][x0];
	y0--;
	distance=-1;
	getDistance();
	step++;
	method='u';
	return true;
}
bool Eight::moveRight(){
	if(x0>1)return false;
	matrix[y0][x0]^=matrix[y0][x0+1];
	matrix[y0][x0+1]^=matrix[y0][x0];
	matrix[y0][x0]^=matrix[y0][x0+1];
	x0++;
	distance=-1;
	getDistance();
	step++;
	method='r';
	return true;
}
bool Eight::moveDown(){
	if(y0>1)return false;
	matrix[y0][x0]^=matrix[y0+1][x0];
	matrix[y0+1][x0]^=matrix[y0][x0];
	matrix[y0][x0]^=matrix[y0+1][x0];
	y0++;
	distance=-1;
	getDistance();
	step++;
	method='d';
	return true;
}
bool Eight::moveLeft(){
	if(x0<1)return false;
	matrix[y0][x0]^=matrix[y0][x0-1];
	matrix[y0][x0-1]^=matrix[y0][x0];
	matrix[y0][x0]^=matrix[y0][x0-1];
	x0--;
	distance=-1;
	getDistance();
	step++;
	method='l';
	return true;
}
vector<Eight> Eight::getNextStatus()const{
	vector<Eight> nextStatus;
	Eight s;
	s=*this;
	if(s.moveLeft())
		nextStatus.push_back(s);
	s=*this;
	if(s.moveUp())
		nextStatus.push_back(s);
	s=*this;
	if(s.moveRight())
		nextStatus.push_back(s);
	s=*this;
	if(s.moveDown())
		nextStatus.push_back(s);
	return nextStatus;
}
bool Eight::operator ==(Eight& b)const{
	for(int i=0;i<3;i++){
		for(int j=0;j<3;j++){
			if(matrix[i][j]!=b.matrix[i][j]){
				return false;
			}
		}
	}
	return true;
}

int Eight::getValue()const{
	int v=0,i,j;
	for(i=0;i<3;i++){
		for(j=0;j<3;j++){
			v*=10;
			v+=matrix[i][j];
		}
	}
	return v;
}

int Eight::getStep()const{
	return step;
}
void Eight::setStep(int s){
	step=s;
}

bool operator < (Eight a,Eight b){
	return a.getValue()<b.getValue();
}

class EightWeightCompare{
public:
	bool operator () (Eight a,Eight b){
		return a.getDistance()+a.getStep()>b.getDistance()+b.getStep();
	}
};

priority_queue<Eight,vector<Eight>,EightWeightCompare> searchQueue;
map<Eight,Eight> previous;

int main(){
	int i,j;
	bool found;
	Eight beginStatus,currentStatus;
	char mx[3][3]={
		{2,8,3},
		{1,0,4},
		{7,6,5}
	},str[3];
	while(~scanf("%s",str)){
		for(i=0;i<3;i++){
			for(j=0;j<3;j++){
				if(i||j)
					scanf("%s",str);
				if(str[0]=='x')
					mx[i][j]=0;
				else
					mx[i][j]=str[0]-'0';
			}
		}
		beginStatus=mx;
		if(beginStatus.getDistance()==0){
			puts("");
			continue;
		}
		while(!searchQueue.empty())searchQueue.pop();
		previous.clear();
		found=false;
		searchQueue.push(beginStatus);
		previous[beginStatus]=beginStatus;
	//	beginStatus.print();
		vector<Eight> nextStatus;
		while(!searchQueue.empty()){
		//	puts("---");
			currentStatus=searchQueue.top();
			searchQueue.pop();
		//	currentStatus.print();
		//	puts("---");
			nextStatus=currentStatus.getNextStatus();
			for(i=0;i<nextStatus.size();i++){
				if(previous.find(nextStatus[i])==previous.end()){
		//			nextStatus[i].print();
					previous[nextStatus[i]]=currentStatus;
					if(nextStatus[i].getDistance()==0){
						currentStatus=nextStatus[i];
						found=true;
						break;
					}
					searchQueue.push(nextStatus[i]);
				}
			}
			if(found)break;
		//	puts("***");
		//	getchar();
		}
		if(found){
			nextStatus.clear();
			while(!(currentStatus==previous[currentStatus])){
				nextStatus.push_back(currentStatus);
				currentStatus=previous[currentStatus];
			}
			while(!nextStatus.empty()){
				nextStatus.back().print();
				nextStatus.pop_back();
			}
			puts("");
		}else{
			printf("unsolvable\n");
		}
	}
	return 0;
}

弱弱地说，无解的情况是不存在的，开始我并没写unsolvable。

具体的说明就懒了，因为是很入门的题目。值得一提的是getDistance这个方法，两种写法的性能相去甚远。

发发感慨吧。其实ACM做题真的不会写类的，一点不喜欢这样，宁愿全部公开写struct，但是，为什么工程上喜欢类呢，还各种封装？隐藏真的只是为了隐私么？其实，我觉得根本不是。在多人合作的项目里面，隐藏一部分东西，别人就从编译的角度上无法用代码调用你的这些内容了，而公开的，是你规定好的接口，内部实现别人压根看不到，也管不着。所以，每当你的代码升级了，只要你声明的功能的接口没有改变，对方就不用改变了，封装能够很明显地降低耦合性。