题目 1176: 魔板

 #include<stdio.h>

#include<string.h>

#define MAXN 40330 // 8! + 10

#define MAXL 8

struct {

    char str[MAXL + 1];

    char opt;

    int par;

} queue[MAXN], tmp, nxt;

int fac[] = { 1, 1, 2, 6, 24, 120, 720, 5040 };

int vis[MAXN];

char opt[] = "ABC";

char aim[MAXL + 1];

void(*fun[3])(char *str);

int hash(char *str) {

    int i, j, cnt, sum = 0;

    for (i = 0; i < MAXL; ++i) {

        for (cnt = 0, j = i + 1; j < MAXL; ++j) {

            if (str[j] > str[i]) ++cnt;

        }

        sum += cnt * fac[MAXL - i - 1];

    }

    if (vis[sum]) return 1;

    vis[sum] = 1;

    return 0;

}

void swap(char *a, char *b) {

    char tmp = *a;

    *a = *b;

    *b = tmp;

}

void optA(char *str) {

    swap(&str[0], &str[4]);

    swap(&str[1], &str[5]);

    swap(&str[2], &str[6]);

    swap(&str[3], &str[7]);

}

void optB(char *str) {

    int i;

    char tmp;

    for (tmp = str[3], i = 3; i > 0; --i) {

        str[i] = str[i - 1];

    }

    str[0] = tmp;

    for (tmp = str[7], i = 7; i > 4; --i) {

        str[i] = str[i - 1];

    }

    str[4] = tmp;

}

void optC(char *str) {

    char tmp = str[1];

    str[1] = str[5];

    str[5] = str[6];

    str[6] = str[2];

    str[2] = tmp;

}

void print(int k) {

    if (queue[k].par == -1) return;

    print(queue[k].par);

    printf("%c", queue[k].opt);

}

void bfs() {

    int front = 0, rear = 0, i;

    tmp.opt = 0;

    tmp.par = -1;

    if (!strcmp(tmp.str, aim)) return;

    hash(tmp.str);

    queue[rear++] = tmp;

    while (front != rear) {

        tmp = queue[front];

        for (i = 0; i < 3; ++i) {

            nxt = tmp;

            (*fun[i])(nxt.str);

            if (hash(nxt.str)) continue;

            nxt.opt = opt[i];

            nxt.par = front;

            queue[rear] = nxt;

            if (!strcmp(nxt.str, aim)) {

                print(rear);

                return;

            }

            ++rear;

        }

        ++front;

    }

}

int main() {

    fun[0] = optA;

    fun[1] = optB;

    fun[2] = optC;

    while (scanf("%s", tmp.str) != EOF) {

        scanf("%s", aim);

        swap(&tmp.str[4], &tmp.str[7]);

        swap(&tmp.str[5], &tmp.str[6]);

        swap(&aim[4], &aim[7]);

        swap(&aim[5], &aim[6]);

        memset(vis, 0, sizeof(vis));

        bfs();

        printf("\n");

    }

    return 0;

}