HDU 1043 Eight

康复计划之搜索 1
因为有个小学弟在第二天就说ida * 看不懂，搞得我挺慌 我可以说我也不是很熟么

题意：
经典八数码

思路：
这里提供的是单向bfs + 打表思路，本来想复习ida * 但是不小心看到了kuangbin的思路，就写了一下。

简单说就是我从起始状态 123456780 开始对0进行bfs，通过康托展开的hash函数进行记录状态和路径。询问时对哈希值进行询问和查找。

实际上并没有用到康托展开的性质，只是通过2进制hash而已……

#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <string>

using namespace std;
const int maxn = 400000;

int fac[] = { 0, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880 };
string path[maxn];
bool vis[maxn];
int dx[] = { 0, -1, 0, 1 };
int dy[] = { -1, 0, 1, 0 };
char dir[] = "rdlu";

struct node {
    int s[9];
    int zero_pos;
    int hash;
    string path;
};

int cantor_hash(int s[])
{
    int res = 0;
    for (int i = 0; i < 9; i++) {
        int renum = 0;
        for (int j = i + 1; j < 9; j++)
            if (s[i] > s[j])
                renum++;
        res += (renum * fac[9 - i - 1]);
    }
    return res;
}

void init()
{
    memset(vis, false, sizeof vis);
    node cur, nxt;
    for (int i = 0; i < 8; i++)
        cur.s[i] = i + 1;
    cur.s[8] = 0;
    cur.zero_pos = 8;
    cur.hash = cantor_hash(cur.s);
    path[cur.hash] = "";
    vis[cur.hash] = true;
    queue<node> que;
    que.push(cur);
    while (!que.empty()) {
        cur = que.front();
        que.pop();
        int x = cur.zero_pos / 3;
        int y = cur.zero_pos % 3;
        for (int i = 0; i < 4; i++) {
            int xx = x + dx[i];
            int yy = y + dy[i];
            if (xx < 0 || xx > 2 || yy < 0 || yy > 2)
                continue;
            nxt = cur;
            nxt.zero_pos = xx * 3 + yy;
            nxt.s[cur.zero_pos] = nxt.s[nxt.zero_pos];
            nxt.s[nxt.zero_pos] = 0;
            nxt.hash = cantor_hash(nxt.s);
            if (!vis[nxt.hash]) {
                nxt.path = dir[i] + cur.path;
                path[nxt.hash] = nxt.path;
                que.push(nxt);
                vis[nxt.hash] = true;
            }
        }
    }
}

int main()
{
    init();
    node cur;
    char buf[2];
    while (scanf("%s", buf) != EOF) {
        if (buf[0] == 'x') {
            cur.zero_pos = 0;
            cur.s[0] = 0;
        } else
            cur.s[0] = buf[0] - '0';
        for (int i = 1; i < 9; i++) {
            scanf("%s", buf);
            if (buf[0] == 'x') {
                cur.zero_pos = i;
                cur.s[i] = 0;
            } else
                cur.s[i] = buf[0] - '0';
        }
        cur.hash = cantor_hash(cur.s);
        //cout << cur.hash << endl;
        if (vis[cur.hash])
            cout << path[cur.hash] << endl;
        else
            puts("unsolvable");
    }
    return 0;
}