八数码问题【康托展开+BFS】

/ Vijos / 题库 / 八数码问题

背景

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

描述

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

格式

输入格式

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

输出格式

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

样例1

样例输入1

283104765

Copy

样例输出1

4

  尽管这道题的题意上说要用启发式搜索来做，但是我没有启发的idea！直接暴力康托展开加上BFS，然后直接输出答案，因为时间复杂度最高就是O(9 !)所以，还是暴力吧。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
#define INF 0x3f3f3f3f
#define HalF (l + r)>>1
#define lsn rt<<1
#define rsn rt<<1|1
#define Lson lsn, l, mid
#define Rson rsn, mid+1, r
#define QL Lson, ql, qr
#define QR Rson, ql, qr
#define myself rt, l, r
#define MP(x, y) make_pair(x, y)
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int maxN = 363000;
const int dir[4][2] =
{
    -1, 0,
    0, -1,
    0, 1,
    1, 0
};
int jc[10];
string ans[maxN];
int step[maxN];
bool vis[maxN];
inline int Cantor(int len, string a)    //康托展开
{
    int tmp, sum = 0;
    for(int i=0; i<len; i++)
    {
        tmp = 0;
        for(int j=i+1; j<len; j++)
        {
            if(a[i] > a[j]) tmp++;
        }
        sum += tmp * jc[len - i - 1];
    }
    return sum + 1; //排名+1
}
inline int _id(int x, int y) { return (x - 1) * 3 + y - 1; }
inline bool In_map(int x, int y) { return x > 0 && y > 0 && x <= 3 && y <= 3; }
struct node
{
    int x0, y0;
    string s;
    node(int a=0, int b=0, string c=""):x0(a), y0(b), s(c) {}
};
inline void bfs()
{
    node now = node(2, 2, "123804765"), nex;
    queue<node> Q;
    Q.push(now);
    int sta = Cantor(9, now.s), las;
    vis[sta] = true; step[sta] = 0;
    while(!Q.empty())
    {
        now = Q.front(); Q.pop();
        sta = Cantor(9, now.s);
        for(int i=0, xx, yy; i<4; i++)
        {
            xx = now.x0 + dir[i][0]; yy = now.y0 + dir[i][1];
            if(!In_map(xx, yy)) continue;
            nex = now;
            swap(nex.s[_id(now.x0, now.y0)], nex.s[_id(xx, yy)]);
            nex.x0 = xx; nex.y0 = yy;
            las = Cantor(9, nex.s);
            if(!vis[las])
            {
                vis[las] = true;
                step[las] = step[sta] + 1;
                Q.push(nex);
            }
        }
    }
}
int F[10];
string A;
int main()
{
//    freopen("cowjog.in", "r", stdin);
//    freopen("cowjog.out", "w", stdout);
    jc[0] = jc[1] = 1;
    for(int i=2; i<=9; i++) jc[i] = jc[i-1] * i;
    memset(vis, false, sizeof(vis));
    bfs();
    cin>>A;
    printf("%d\n", step[Cantor(9, A)]);
    return 0;
}