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; 
                step[order_change][1] = order; 
                if(order_change == order_dest) 
                    return; 
            } 
        } 
    } 
} 
 
int main() 
{ 
    char input[10]; 
    int i=5,j=0; 
    int order = 0; 
    int order_start; 
    int order_dest = getOrder("123456789"); 
    char state[10]; 
    char map[4] = {'u','d','l','r'}; 
 
    scanf("%c %c %c %c %c %c %c %c %c",input,input+1,input+2,input+3,input+4,input+5,input+6,input+7,input+8); 
    i = strchr(input,'x') - input; 
    input[i] = '9'; 
    order_start = getOrder(input); 
    bfs(input,i); 
    if(!visit[order_dest]){ 
        printf("unsolvable\n"); 
        return 0; 
    } 
    //回溯 
    order =  order_dest; 
    while(order != order_start){ 
        step1[j++] = step[order][0];         
        order = step[order][1];  
    } 
    for(j -= 1;j>=0;j--){ 
        printf("%c",map[ step1[j] ]); 
    } 
    printf("\n"); 
    return 1; 
}