zzc


私信TA

用户名:zzc111

访问量:1736

签 名:

等  级
排  名 825
经  验 3458
参赛次数 0
文章发表 8
年  龄 13
在职情况 学生
学  校 幸福湖小学
专  业

  自我简介:

TA的其他文章

题目 1176: 魔板
浏览:95

 #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;

}


 

0.0分

1 人评分

  评论区