POJ 1077 Eight 八数码问题[康托展开 + BFS]

POJ 1077 Eight 八数码问题 [康托展开 + BFS]

题目链接：Here！

对于八数码问题，可能问题的关键不是BFS，而是对状态的标记。八数码的状态恰好是一个全排列，那么对于全排列，康托展开就是一个完美的哈希。

康托展开：X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! ，其中a[i]为当前未出现的元素中是排在第几个（从0开始）。这就是康托展开。

其实康托展开就是利用全排列的性质从高位向低位求第N大数或者第N小数。

#include <map>
#include <vector>
#include <queue>
#include <cmath>
#include <cstdio>
#include <string>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
using namespace std;

//#pragma comment(linker, "/STACK:1024000000,1024000000")

#define FIN             freopen("input.txt","r",stdin)
#define FOUT            freopen("output.txt","w",stdout)
#define CASE(T)         for(scanf("%d",&T);T--;)
#define fst             first
#define snd             second

#define lson            l, mid, rt << 1
#define rson            mid+1, r, rt << 1 | 1

typedef __int64  LL;
//typedef long long LL;
typedef pair<int, int> PII;

const int MAXN = 9;
const int dir[] = { -3, -1, 1, 3};
const char H[] = "ulrd";
char src[MAXN], dest[MAXN];
const int MAXM = 1e6;
struct Node {
    int xpos, step;
    char grid[MAXN];
    string res;
    int contorV;
} cur, rear;

int T, R, C;

char str[MAXN];
queue<Node> Q;
int fact[10];
bool vis[MAXM];
void init() {
    fact[0] = 1;
    for(int i = 1; i < 10; i ++) {
        fact[i] = fact[i - 1] * i;
    }
}

/// contor展开求第N小数
int contor(const char s[]) {
    int ret = 0, temp;
    for(int i = 0; i < 9; i ++) {
        temp = 0;
        for(int j = i + 1; j < 9; j ++) {
            if(s[i] > s[j]) temp ++;
        }
        ret += temp * fact[9 - i - 1];
    }
    return ret + 1;
}

const int contor_dest = contor("123456789");

inline bool outRange(int x) {
    return x < 0 || x >= 9;
}
/// 除去不是从相邻位置过来的情况
inline bool check(int x1, int y1, int x2, int y2) {
    return ((x1 == x2) && abs(y1 - y2) == 1) || ((y1 == y2) && abs(x1 - x2) == 1);
}

int bfs() {
    memset(vis, false, sizeof(vis));
    int ret = -1;
    vis[cur.contorV = contor(cur.grid)] = true;
    cur.step = 0;
    Q.push(cur);
    while(!Q.empty()) {
        cur = Q.front();
        Q.pop();
        if(~ret) continue;
        if(cur.contorV == contor_dest) {
            ret = cur.step;
            cout << cur.res << endl;
            continue;
        }
        int x1, x2, y1, y2;
        x1 = cur.xpos / 3;
        y1 = cur.xpos % 3;
        for(int i = 0; i < 4; i++) {
            rear.xpos = cur.xpos + dir[i];
            x2 = rear.xpos / 3;
            y2 = rear.xpos % 3;
            if(outRange(rear.xpos)) continue;
            strcpy(rear.grid, cur.grid);
            swap(rear.grid[rear.xpos], rear.grid[cur.xpos]);
            if(!check(x1, y1, x2, y2)) continue;
            int val = rear.contorV = contor(rear.grid);
            if(vis[val]) continue;
            vis[val] = true;
            rear.step = cur.step + 1;
            rear.res = cur.res + H[i];
            Q.push(rear);
        }
    }
    return ret;
}

int main() {
#ifndef ONLINE_JUDGE
    FIN;
#endif // ONLINE_JUDGE
    init();

    while(~scanf("%s", str)) {
        cur.res = "";
        if(str[0] == 'x') {
            cur.xpos = 0;
            str[0] = '9';
        }
        cur.grid[0] = str[0];
        for(int i = 1; i < 9; i++) {
            scanf("%s", str);
            if(str[0] == 'x') {
                cur.xpos = i;
                str[0] = '9';
            }
            cur.grid[i] = str[0];
        }
        int ret = bfs();
        if(ret == -1) puts("unsolvable");
    }
    return 0;
}