cube_felicia.cpp

第四届百度杯预赛解题报告 武汉大学20090315

/**********************************************************************
Author: Felicia
Created Time:  2009-2-19 16:00:32
File Name: whu09_4.cpp
Description: 
**********************************************************************/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>

using namespace std;

#define SZ(a) (int)((a).size())

typedef long long int64;
const int maxint = 0x7FFFFFFF;
const int64 maxint64 = 0x7FFFFFFFFFFFFFFFLL;

const int P = 61;
const int M = 502973;

const int r[12][3][4] =
{
    {{0, 1, 2, 3}, {17, 13, 9, 5}, {16, 12, 8, 4}},
    {{3, 2, 1, 0}, {5, 9, 13, 17}, {4, 8, 12, 16}},
    {{4, 5, 6, 7}, {0, 8, 20, 18}, {3, 11, 23, 17}},
    {{7, 6, 5, 4}, {18, 20, 8, 0}, {17, 23, 11, 3}},
    {{8, 9, 10, 11}, {2, 15, 20, 5}, {3, 12, 21, 6}},
    {{11, 10, 9, 8}, {5, 20, 15, 2}, {6, 21, 12, 3}},
    {{12, 13, 14, 15}, {9, 1, 19, 21}, {10, 2, 16, 22}},
    {{15, 14, 13, 12}, {21, 19, 1, 9}, {22, 16, 2, 10}},
    {{16, 17, 18, 19}, {1, 4, 23, 14}, {0, 7, 22, 13}},
    {{19, 18, 17, 16}, {14, 23, 4, 1}, {13, 22, 7, 0}},
    {{20, 21, 22, 23}, {6, 10, 14, 18}, {7, 11, 15, 19}},
    {{23, 22, 21, 20}, {18, 14, 10, 6}, {19, 15, 11, 7}}
};

const int change[24] = {
          0,  1,
          3,  2,
  4,  5,  8,  9, 12, 13, 16, 17,
  7,  6, 11, 10, 15, 14, 19, 18,
         20, 21,
         23, 22
};
struct cube {
    char a[24];
    cube() {}
    bool operator ==(const cube &b) const {
        for (int i = 0; i < 24; i++)
            if (a[i] != b.a[i])
                return false;
        return true;
    }
    int read() {
        char buf[10];
        for (int i = 0; i < 24; i++) {
            int t = scanf("%s", buf);
            if (t == EOF)
                return EOF;
            a[change[i]] = buf[0];
        }
        return 0;
    }
};

void rotate(int d, cube &a) {
    for (int i = 0; i < 3; i++) {
        int t = a.a[r[d][i][0]];
        a.a[r[d][i][0]] = a.a[r[d][i][1]];
        a.a[r[d][i][1]] = a.a[r[d][i][2]];
        a.a[r[d][i][2]] = a.a[r[d][i][3]];
        a.a[r[d][i][3]] = t;
    }
}


vector <cube> hash_table[M];
vector <int> hash_table_step[M];

int hash(const cube &a) {
    int ret = 0;
    for (int i = 0; i < 24; i++) {
        ret = (ret + a.a[i]) * P % M;
    }
    return ret;
}

bool find(const cube &a, const int &step, int &ret) {
    int h = hash(a);
    for (int i = 0; i < SZ(hash_table[h]); i++)
        if (a == hash_table[h][i]) {
            ret = hash_table_step[h][i];
            return true;
        }
    hash_table[h].push_back(a);
    hash_table_step[h].push_back(step);
    return false;
}

void clear() {
    for (int i = 0; i < M; i++) {
        hash_table[i].clear();
        hash_table_step[i].clear();
    }
}

cube qa[3000000];
cube qb[3000000];

int bfs(const cube &st, const cube &ed) {
    if (st == ed)
        return 0;
    int la = 0, ra = 1, mida = 1, stepa = 0;
    int lb = 0, rb = 1, midb = 1, stepb = 0;
    qa[la] = st;
    qb[lb] = ed;
    clear();
    hash_table[hash(st)].push_back(st);
    hash_table_step[hash(st)].push_back(0);
    hash_table[hash(ed)].push_back(ed);
    hash_table_step[hash(ed)].push_back(0);

    int ts;
    while (1) {
        stepa++;
        for (int i = la; i < mida; i++) {
            for (int j = 0; j < 12; j++) {
                cube t = qa[i];
                rotate(j, t);
                if (!find(t, stepa, ts)) {
                    qa[ra++] = t;
                }
                else if (ts < 0) {
                    return stepa - ts;
                }
            }
        }
        la = mida;
        mida = ra;
        
        stepb++;
        for (int i = lb; i < midb; i++) {
            for (int j = 0; j < 12; j++) {
                cube t = qb[i];
                rotate(j, t);
                if (!find(t, -stepb, ts)) {
                    qb[rb++] = t;
                }
                else if (ts > 0) {
                    return stepb + ts;
                }
            }
        }
        lb = midb;
        midb = rb;
    }
    return -1;
}

int main() {
    int ca;
    scanf("%d", &ca);
    while (ca--) {
        cube st, ed;
        if (st.read() == EOF)
            break;
        ed.read();
        printf("%d\n", bfs(st, ed));
    }
    return 0;
}