Magic Square 解题报告

本题是BFS的经典题目，因为只有8个数字，每个都在1～8之间，因此可以使用一个32bit整型描述状态，使用bitwise改变状态。

需要注意散列函数，要使用unsigned long，或者给返回值加上labs()，否则散列值（在某些机器上）可能是负数，造成数组越界。

代码如下：

#include <stdio.h>
#include <stdlib.h>
#define SEED 10007

struct element
{
    unsigned long s;
    char op;
    long prev;
}queue[41000] = {};

struct HNode
{
    unsigned long s;
    struct HNode *next;
}*hashtable[SEED] = {};

long head,tail;
long target = 0;

void enqueue(struct element a)
{
    queue[tail ++] = a;
}

struct element dequeue()
{
    return queue[head ++];
}

void getarget()
{
    int i;
    long t;
    for(i = 7;i >= 0;i --)
    {
        scanf("%ld",&t);
        target |= t << (i * 4);
    }
}

unsigned long h(unsigned long s)
{
    return (s % (unsigned long)SEED);
}

long transA(long s)
{
    long t;
    t = ((s & 0xF) << 28) | ((s & 0xF0) << 20) | ((s & 0xF00) << 12) | ((s & 0xF000) << 4);
    t |= ((s & 0xF0000) >> 4) | ((s & 0xF00000) >> 12) | ((s & 0xF000000) >> 20) | ((s & 0xF0000000) >> 28);
    return t;
}

long transB(long s)
{
    long t;
    t = ((s & 0xFFF00000) >> 4) + ((s & 0xFFF) << 4) + ((s & 0xF0000) << 12) + ((s & 0xF000) >> 12);
    return t;
}

long transC(long s)
{
    long t;
    t = s & 0xF00FF00F;
    t |= (s & 0xF0) << 20 | (s & 0xF00) >> 4 | (s & 0xF00000) >> 12 | (s & 0xF000000) >> 4;
    return t;
}

void pt(struct element p)
{
    char str[70];
    int i;
    for(i = 0;i < 60 && p.op != 0;p = queue[p.prev],i ++)
    {
        str[i] = p.op;
    }
    printf("%d\n",i);
    for(i --;i >= 0;i --)
    {
        printf("%c",str[i]);
    }
    printf("\n");
}

int find(long s)
{
    struct HNode *p;
    for(p = hashtable[h(s)];p != NULL;p = p->next)
        if(p->s == s)   return 1;
    return 0;
}

void insert(long s)
{
    struct HNode *p;
    p = malloc(sizeof(struct HNode));
    p->s = s;
    p->next = hashtable[h(s)];
    //fprintf(stderr,"%ld\n",h(s));
    hashtable[h(s)] = p;
}

int main()
{
    freopen("msquare.out","w",stdout);
    freopen("msquare.in","r",stdin);
    struct element now,next;
    long tmp;
    head = tail = 0;
    getarget();
    now.s = 0x12345678;
    now.prev = 0;
    now.op = 0;
    insert(0x12345678);
    enqueue(now);
    while(head < tail)
    {
        now = dequeue();
        if(now.s == target) break;
        tmp = transA(now.s);
        if(!find(tmp))
        {
            insert(tmp);
            next.s = tmp;
            next.prev = head - 1;
            next.op = 'A';
            enqueue(next);
        }
        tmp = transB(now.s);
        if(!find(tmp))
        {
            insert(tmp);
            next.s = tmp;
            next.prev = head - 1;
            next.op = 'B';
            enqueue(next);
        }
        tmp = transC(now.s);
        if(!find(tmp))
        {
            insert(tmp);
            next.s = tmp;
            next.prev = head - 1;
            next.op = 'C';
            enqueue(next);
        }
    }
    pt(now);
    return 0;
}

此外，USACO的题解给出了一种更适用与本题的方法，即把每个状态与一个数字相对应，只要用8！个数字就可以描述所有状态。并且从目标向初始状态搜索，输出结果时就没有必要反过来了。