八数码问题

#include <algorithm>
#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>
#include <set>
using namespace std;

class State {
public:
#define ARR_NUM 9
	State(const int arr[], State* father = NULL) {
		this->father = father;
		memcpy(this->arr, arr, ARR_NUM * sizeof(int));
	}
	void getNewState(vector<State*>& vec) {
		int zero = 0;
		for (int i = 0; i < ARR_NUM; ++i) if (arr[i] == 0) {
			zero = i;break;
		}
		int x = zero / 3, y = zero % 3;
		int temp[ARR_NUM] = {0};
		const int dx[] = {-1, 0, 1,  0};
		const int dy[] = { 0, 1, 0, -1};
		for (int i = 0; i < 4; ++i) {
			int newx = x + dx[i];
			int newy = y + dy[i];
			int newIndex = newx * 3 + newy;
			if (newx >= 0 && newx < 3 && newy >= 0 && newy < 3) {
				memcpy(temp, arr, ARR_NUM * sizeof(int));
				temp[zero] = temp[newIndex];
				temp[newIndex] = 0;
				vec.push_back(new State(temp, this));
			}
		}
	}
	bool equal(const State state) {
		return (memcmp(this->arr, state.arr, ARR_NUM * sizeof(int)) == 0);
	}
	void printState() {
		for (int i = 0; i < ARR_NUM; ++i) {
			printf("%d ", arr[i]);
		}
		printf("\n");
	}
	bool operator < (const State& state) const {
		return memcmp(arr, state.arr, ARR_NUM * sizeof(int)) < 0;
	}

	int arr[ARR_NUM];
	State* father;
};

void f(State* pStart, State* pEnd) {
	queue<State*> q;
	set<State> s;
	q.push(pStart);
	while (!q.empty()) {
		State* f = q.front();
		if (s.count(*f) > 0) {
			q.pop();
			continue;
		} else {
			s.insert(*f);
		}
		if (f->equal(*pEnd)) {
			int count = 0;
			State* p = f->father;
			while(p) {
				p = p->father;
				++count;
			}
			printf("suc: %d\n", count);
			break;
		}
		vector<State*> v;
		f->getNewState(v);
		for (vector<State*>::const_iterator i = v.begin(); i != v.end(); ++i) {
			q.push(*i);
		}
		q.pop();
	}
}

int main()
{
	int a[9] = {0};
	int b[9] = {0};
	for (int i = 0; i < 9; ++i) {
		scanf("%d", &a[i]);
	}
	for (int i = 0; i < 9; ++i) {
		scanf("%d", &b[i]);
	}
	State* pStart = new State(a);
	State* pEnd = new State(b);
	f(pStart, pEnd);
	return 0;
}