sicily 2011

刚开始做是对每一组数据直接进行bfs，结果TLE，后来改成先对所有情况进行bfs，然后直接由康拓展开输出答案，还是TLE。。后来，不用cin cout流。。AC...

#include <cstdio>
#include <cstring>
using namespace std;
struct node {
    int s[9];
    int step;
}q[362880];
int ans[362880];
int init[9];
int tar[9] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
int fac[9];
bool isUsed[362880];
void setFac() {
    fac[0] = fac[1] = 1;
    for(int i = 2; i <= 8; i++) fac[i] = fac[i - 1] * i;
}
int getID(int *data) {
    int id = 0;
    for(int i = 0; i < 9; i++) {
		int k = 0;
        for(int j = i + 1; j < 9; j++) {
            if(data[j] < data[i]) k++;
        }
		id += fac[9 - i - 1] * k;
    }
    return id;
}
void bfs() {
    node front;
	memset(isUsed, false, sizeof(isUsed));
    memcpy(front.s, tar, sizeof(tar));
    front.step = 0;
    q[0] = front;
    int id = getID(tar);
    isUsed[id] = true;
	ans[id] = 0;
    int beg = 0, end = 1;
    while(beg < end) {
        node tmp;
        tmp.step = q[beg].step + 1;
        tmp.s[0] = q[beg].s[1];
        tmp.s[1] = q[beg].s[4];
        tmp.s[2] = q[beg].s[2];
        tmp.s[3] = q[beg].s[0];
        tmp.s[4] = q[beg].s[3];
        tmp.s[5] = q[beg].s[5];
        tmp.s[6] = q[beg].s[6];
        tmp.s[7] = q[beg].s[7];
        tmp.s[8] = q[beg].s[8];
        id = getID(tmp.s);
        if(!isUsed[id]) {
            q[end++] = tmp;
            ans[id] = tmp.step;
            isUsed[id] = true;
        }
        tmp.s[0] = q[beg].s[0];
        tmp.s[1] = q[beg].s[2];
        tmp.s[2] = q[beg].s[5];
        tmp.s[3] = q[beg].s[3];
        tmp.s[4] = q[beg].s[1];
        tmp.s[5] = q[beg].s[4];
        tmp.s[6] = q[beg].s[6];
        tmp.s[7] = q[beg].s[7];
        tmp.s[8] = q[beg].s[8];
        id = getID(tmp.s);
        if(!isUsed[id]) {
            q[end++] = tmp;
            ans[id] = tmp.step;
            isUsed[id] = true;
        }
        tmp.s[0] = q[beg].s[0];
        tmp.s[1] = q[beg].s[1];
        tmp.s[2] = q[beg].s[2];
        tmp.s[3] = q[beg].s[4];
        tmp.s[4] = q[beg].s[7];
        tmp.s[5] = q[beg].s[5];
        tmp.s[6] = q[beg].s[3];
        tmp.s[7] = q[beg].s[6];
        tmp.s[8] = q[beg].s[8];
        id = getID(tmp.s);
        if(!isUsed[id]) {
            q[end++] = tmp;
            ans[id] = tmp.step;
            isUsed[id] = true;
        }
        tmp.s[0] = q[beg].s[0];
        tmp.s[1] = q[beg].s[1];
        tmp.s[2] = q[beg].s[2];
        tmp.s[3] = q[beg].s[3];
        tmp.s[4] = q[beg].s[5];
        tmp.s[5] = q[beg].s[8];
        tmp.s[6] = q[beg].s[6];
        tmp.s[7] = q[beg].s[4];
        tmp.s[8] = q[beg].s[7];
        id = getID(tmp.s);
        if(!isUsed[id]) {
            q[end++] = tmp;
            ans[id] = tmp.step;
            isUsed[id] = true;
        }
        beg++;
    }
}
int main() {
    setFac();
    bfs();
    while(scanf("%d", &init[0]) == 1){
        for(int i = 1; i < 9; i++) scanf("%d", &init[i]);
        printf("%d/n", ans[getID(init)]);
    }
	return 0;
}