POJ 1077 eight 拼图游戏 BFS

描述： POJ 1077

3X3的方格中，其中8个格子是1～8，另外一个格子为X，X只能和与其相邻的上下左右四个方向的格子互换位置，求一种调整方案，使得拼图复原，及12345678X。下图是4X4的情况，

研究遍历算法，首先要弄清楚要遍历的状态个数有多少，对于3X3的格子，状态数有9！，而不是9个。

首先我们要建立一个映射，将9！中状态分别一一映射为一个整数，用到的是康托展开，在此不再赘述，所以我们要维护一个长度为9！的队列，进行BFS即可。

[cpp]
//4100K 625MS 3386B
//BFS+康托拓展
//难度    三颗星
#include <stdio.h>
#include <string.h>
#define MAX (362880+10)

int queen[MAX];
char visit[MAX];
int step[MAX][2]; //记录
char step1[MAX];    //逆序

//求阶乘
int factorial(int n)
{
    if(1 == n || 0 == n){
        return 1;
    }
    return n*factorial(n-1);
}
//求数组state中为0且下标比a小的数的个数
//a:1~9
int getLessSum(char *visit,int a)
{
    int i;
    int reval=0;
    for(i=0;i<a-1;i++){
        reval += (!visit[i])? 1 : 0;
    }
    return reval;
}
//求状态对应全排列的序数
int getOrder(char *state){
    int i;
    char visit[9] = {0};//表示1~9是否已经用过
    int lessSum;
    int reval = 0;

    for(i=0;i<9;i++){
        lessSum = getLessSum(visit,state[i]-48);
        visit[state[i]-48-1] = 1;
        reval += lessSum*factorial(8-i);
    }
    return reval;
}
//求全排列的序数对应的状态
void getState(char * state,int order)
{
    int num ;       //比当前位小的数的个数
    int factor;
    int cnt=0;
    int i,j;
    char visit[9] = {0};

    for(i=0;i<9;i++){
        factor = factorial(8-i);
        num = order / factor;
        order = order % factor;
        cnt = 0;
        for(j=0;j<9;j++){
            if(!visit[j]){
                if(cnt++ == num){
                    state[i] = 48 + j + 1; //
                    visit[j] = 1;
                    break;
                }
            }
        }
    }
}
void swap(char *a,char *b)
{
    *a ^= *b;
    *b ^= *a;
    *a ^= *b;
}
//四种状态变化，0~3代表上下左右交换
int changeState(char *state,int idx,int n)
{
    char tmp;
    char state_change[10] = {0};
    int order=-1;

    memcpy(state_change,state,10);
    switch(n){
    case 0:
        if(idx - 3 >= 0)
            swap(&state_change[idx],&state_change[idx - 3]);
        break;
    case 1:
        if(idx + 3 <= 8)
            swap(&state_change[idx],&state_change[idx + 3]);
        break;
    case 2:
        if(idx % 3 > 0)
            swap(&state_change[idx],&state_change[idx - 1]);
        break;
    case 3:
        if(idx % 3 < 2)
            swap(&state_change[idx],&state_change[idx + 1]);
        break;
    }
    order = getOrder(state_change);
    return order;
}
//找到x对应的下标 0~8
int getIdx(char *state)
{
    int reval = strchr(state,'9') - state;
    return reval;
}
//idx 指X的位置
void bfs(char *state,int idx)
{
    int head=0,rear=1;
    int order,order_change;
    int order_dest = getOrder("123456789");
    int i;

    order = getOrder(state);
    queen[head] = order;
    visit[order] = 1;
    while(head < rear){
        order = queen[head++]; //出队
        getState(state,order);
        idx = getIdx(state);
        for(i=0;i<4;i++){
            order_change = changeState(state,idx,i);
            if(!visit[order_change] && order_change>=0){
                visit[order_change] = 1;
                queen[rear++] = order_change;   //入队
                step[order_change][0] = i;
        &nbs

补充：软件开发 , C++ ,