codevs1225 八数码难题(A*搜索+康托展开)

题目描述 Description

Yours和zero在研究A*启发式算法.拿到一道经典的A*问题,但是他们不会做,请你帮他们.
问题描述

在3×3的棋盘上，摆有八个棋子，每个棋子上标有1至8的某一数字。棋盘中留有一个空格，空格用0来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局（为了使题目简单,设目标状态为123804765），找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。

输入描述 Input Description

输入初试状态，一行九个数字，空格用0表示

输出描述 Output Description

只有一行，该行只有一个数字，表示从初始状态到目标状态需要的最少移动次数(测试数据中无特殊无法到达目标状态数据)

样例输入 Sample Input

283104765

样例输出 Sample Output

八数码问题是一个经典的搜索问题，解法有多种，如A*，双向广搜等。

我这里用的是A*。

每一步交换最多有一个数到达目标位置（跟0进行交换），因此A*的启发函数可以定义为当前状态与目标状态对应位置不相同的字符个数。

对于状态的表示，这里还用到了一个叫“康托展开”的方法。可以看这里http://blog.csdn.net/zhongkeli/article/details/6966805。其实我觉得维基百科上讲的也挺详细。

简单来说就是将1到n的一个排列映射为一个数x（1<=x<=n!），表示该排列是这n个数的第x个排列。其逆运算是将一个自然数映射成一个排列。

这样就可以方便的存储中间状态了。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <set>
using namespace std;
const int INF = 0x3f3f3f3f;
#define rep(i,f,t) for(int i = (f),_end = (t); i <= _end; ++i)
#define debug(x) cout<<"debug  "<<x<<endl;
#define clr(ct,x) memset(ct,x,sizeof(ct));
typedef long long int64;

const int fac[] = {1,1,2,6,24,120,720,5040,40320,362880};//9!
int Cantor(char vec[]){
    int res = 0;
    rep(i,0,8){
        int cnt = 0;
        rep(j,i+1,8){
            if(vec[j] < vec[i])++cnt;
        }
        res += cnt * fac[8-i];
    }
    return res + 1;
}
void CantorInv(int x,char *res){
    --x;
    bool vis[10] = {0};
    rep(i,1,9){
        int t = x / fac[9-i];
        x %= fac[9-i];
        int j,cnt = 0;
        for(j = 1; cnt <= t; ++j){
            if(!vis[j])++cnt;
        }
        vis[--j] = 1;
        *(res++) = j+'0'-1;
    }
}
char  resstr[] = {"123804765"};
char mp[3][3];
int res;
bool vis[400000];
struct Node{
    int sta,d,h;
    bool operator<(const Node& n2)const{
        return d+h > n2.d+n2.h;
    }
    Node(int s,int dd,int hh):sta(s),d(dd),h(hh){}
};
int hf(){
    char* sm = mp[0];
    const char* sr = resstr;
    int rs = 0;
    rep(i,0,8){
        if(sm[i] != sr[i])++rs;
    }
    return rs-1;
}
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};
int solve(){
    priority_queue<Node> q;
    int ct = Cantor(mp[0]);if(ct == res)return 0;
    q.push(Node(ct,0,hf()));
    clr(vis,0);
    while(!q.empty()){
        Node no = q.top();q.pop();
        if(no.sta == res)return no.d;
        if(vis[no.sta])continue;
        vis[no.sta] = 1;
        CantorInv(no.sta,mp[0]);
        int x,y;
        rep(i,0,2)rep(j,0,2){
            if(mp[i][j]=='0'){
                x = i;y = j;
                goto ok;
            }
        }
ok:
        rep(k,0,3){
            int tx = x+dx[k],ty = y+dy[k];
            if(tx < 0 || ty < 0)continue;
            if(tx > 2 || ty > 2)continue;
            swap(mp[x][y], mp[tx][ty]);
            ct = Cantor(mp[0]);
            if(!vis[ct]){
                q.push(Node(ct,no.d+1,hf()));
            }
            swap(mp[x][y], mp[tx][ty]);
        }
    }
    return -1;
}
int main(){
    res = Cantor(resstr);
    rep(i,0,2)rep(j,0,2)scanf(" %c",&mp[i][j]);
    int ans = solve();
    cout<<ans<<endl;
    return 0;
}