1868.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1868 on 2006-08-29 at 14:24:16 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

typedef pair<int, int> pii;
const int SN = 362880;
const int nm[] = { 1, 1, 2, 6, 24, 120, 720, 5040, 40320 };
const int DIR[][2] = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
const int CHG[] = { -3, 3, -1, 1 };
 
class Heap {
private:
	int size;
	int p[SN], d[SN], h[SN], t[SN];
	void siftUp(int);
	void siftDown(int);
public:
	void clear() { size = 0; memset(h, -1, sizeof(h)); }
	bool isEmpty() const { return (size == 0); }
	void push(int, int, int);
	pii pop();
};
void Heap::siftUp(int n) {
	int dn = d[n], pn = p[n], tn = t[n], m, i;
	for(i = n; i > 0; i = m) {
		m = (i-1)/2;
		if(dn >= d[m]) break;
		d[i] = d[m]; p[i] = p[m]; t[i] = t[m]; h[p[i]] = i;
	}
	d[i] = dn; p[i] = pn; t[i] = tn; h[pn] = i;
}
void Heap::siftDown(int n) {
	int dn = d[n], pn = p[n], tn = t[n], i, m;
	for(i = n; i < size; i = m) {
		m = 2*i+1;
		if(m >= size) break;
		if(m+1 < size && d[m] > d[m+1]) m++;
		if(dn <= d[m]) break;
		d[i] = d[m]; p[i] = p[m]; t[i] = t[m]; h[p[i]] = i;
	}
	d[i] = dn; p[i] = pn; t[i] = tn; h[pn] = i;
}
void Heap::push(int ps, int pd, int pt) {
	if(h[ps] == -1) {
		h[ps] = size++;
		d[h[ps]] = pd; t[h[ps]] = pt; p[h[ps]] = ps;
		siftUp(h[ps]);
	} else if(h[ps] == -2 || d[h[ps]] <= pd) return;
	else {
		d[h[ps]] = pd; t[h[ps]] = pt;
		siftUp(h[ps]);
	}
}
pii Heap::pop() {
	pii b = pii(p[0], t[0]);
	h[p[0]] = -2; size--;
	if(size != 0) {
		d[0] = d[size]; t[0] = t[size]; p[0] = p[size];
		h[p[0]] = 0;
		siftDown(0);
	}
	return b;
}
 
class Puzzle {
public:
	int board[9], state, zp;
	Puzzle(int);
	void init();
	void hash();
	int back();
	void change(int);
	int f(const Puzzle&);
};
Puzzle::Puzzle(int n = 0) {
	bool used[9] = { false };
	state = n;
	for(int i = 0; i < 9; i++) {
		int k = n / nm[8-i];
		n %= nm[8-i];
		for(int s = -1, j = 0; j < 9; j++) {
			if(used[j]) continue;
			s++;
			if(s == k) {
				used[j] = true; board[i] = j;
				if(j == 0) zp = i;
				break;
			}
		}
	}
}
void Puzzle::init() {
	for(int i = 0; i < 9; i++) scanf("%d", &board[i]);
	hash();
}
void Puzzle::hash() {
	bool used[9] = { false };
	int s = 0;
	for(int i = state = 0; i < 9; i++) {
		for(int j = s = 0; j < 9; j++)
			if(!used[j] && j < board[i]) s++;
		state += s*nm[8-i];
		used[board[i]] = true;
	}
}
int Puzzle::back() {
	int n = 0;
	for(int i = 0; i < 9; i++)
		for(int j = 0; j < i; j++)
			if(board[i]*board[j] != 0 && board[i] > board[j])
				n++;
	return n;
}
void Puzzle::change(int bp) {
	board[zp] = board[bp];
	board[bp] = 0; zp = bp;
	hash();
}
int Puzzle::f(const Puzzle& p) {
	int cost = 0;
	for(int i = 0; i < 9; i++) {
		for(int j = 0; j < 9; j++) {
			if(board[i] != 0 && board[i] == p.board[j]) {
				cost += abs(i/3-j/3) + abs(i%3-j%3);
				break;
			}
		}
	}
	return cost;
}
 
Heap heap;
 
int main()
{
	int t, T;
	Puzzle begin, end;
	
	scanf("%d", &T);
	for(t = 0; t < T; t++) {
		begin.init(); end.init(); heap.clear();
		if((begin.back()-end.back()) % 2 != 0) printf("-1\n");
		else {
			heap.push(begin.state, end.f(begin), 0);
			while(!heap.isEmpty()) {
				pii state = heap.pop();
				int sec = state.second;
				if(state.first == end.state) {
					printf("%d\n", sec);
					break;
				} else {
					Puzzle cur = Puzzle(state.first);
					int r = cur.zp/3, c = cur.zp%3;
					for(int i = 0; i < 4; i++) {
						int cr = r+DIR[i][0], cc = c+DIR[i][1];
						if(cr < 0 || cr >= 3 || cc < 0 || cc >= 3) continue;
						Puzzle p = cur; p.change(p.zp+CHG[i]);
						heap.push(p.state, end.f(p)+sec, sec+1);
					}
				}
			}
		}
	}
	
	return 0;
}