八数码问题

Time limit: 1000 ms

Memory limit: 1 GB

Standard I/O

Content

3×3九宫棋盘，放置数码为1-8的8个棋牌，剩下一个空格，只能通过棋牌向空格的移动来改变棋盘的布局。要求：根据给定初始布局，问：至少移动几次才能从初始布局到达目标布局。

目标布局如下图：

Input Description

3行，每行3个0-8的不重复整数，其中0表示空格所在的位置，数字间用空格隔开，表示初始布局，数据保证该初始布局一定能移到目标布局。

Output Description

一个整数，表示最少移动到目标布局的次数。

Sample

INPUT

0 7 6
8 4 3
5 2 1

OUTPUT

4

Code

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char state[362880]={};//记录是否已拓展过 ,用char节省空间 
char end[9]={8,7,6,5,4,3,2,1,0};//目标序列 从左到右，从上到下 
int endsub;//目标序列在数组中的下标 
int factor[4]={-3,3,-1,1}; //方向 上下左右 
int fac[8]={40320,5040,720,120,24,6,2,1};//阶乘
struct node{
    char list[9];
    int step;
    struct node* next;
};
struct node *head,*rear;
struct node* MakeNode(char *list,int step){
    struct node *p=(struct node *)malloc(sizeof(struct node));
    memcpy(p->list,list,9);
    p->step=step;
    p->next=NULL;
    return p;
}
int ToSub(char *list){//换算为数组下标，康托展开
    int i,j,rank,sub = 0;
    for (i = 0; i < 8; i++) {
        rank = 0;
        for (j = i + 1; j < 9; j++) if (list[j] < list[i]) rank++;
        sub+=rank*fac[i];
    }
    return sub;
}
int GetSpacePos(char *list){//获取空格位置 
    int i;
    for(i=0;i<9;i++) if(list[i]==0) return i;
}
int Move(char *list,int f){//空格向某方向移动 ,返回0表示不可移动 
    int i=GetSpacePos(list);
    if(f==0 && i-3<0 ) return 0;//上
    if(f==1 && i+3>8 ) return 0;//下     
    if(f==2 && (i+1)%3==1) return 0;//左 
    if(f==3 && (i+1)%3==0) return 0;//右 
    list[i]=list[i+factor[f]];
    list[i+factor[f]]=0;
    return 1;
}
int Search(){
    char tmp[9];
    struct node* p;
    int sub,i;
    while(head!=NULL){
        for(i=0;i<4;i++){
            memcpy(tmp,head->list,9);
            if(Move(tmp,i)){
                sub=ToSub(tmp);
                if(sub==endsub) return head->step+1;
                if(state[sub]) continue;
                state[sub]=1;
                p=MakeNode(tmp,head->step+1);
                rear->next=p;
                rear=p;
            }
        }
        p=head;
        head=head->next;
        free(p); 
    }
    return 0;
}
int main(){
    int i;
    char start[9]={}; 
    for(i=0;i<9;i++){
        scanf("%c",&start[i]);
        start[i]-='0';
        getchar();
    }
    endsub=ToSub(end); 
    rear=head=MakeNode(start,0);
    printf("%d",Search());
}