九宫重排 （C++代码）

#include<cstdio>
#include<cstring>
using namespace std;
typedef int state[9];
const int maxn = 10000000;
state st[maxn],goal;
int dist[maxn];
int fact[9];
int vis[maxn];
void init(){
   fact[0]=1;
   for(int i=1;i<9;i++) fact[i]=i*fact[i-1];
}
int try_to_insert(int s){
      int code = 0 ;
      for(int i=0;i<9;i++){
        int cnt =0;
        for(int j=i+1;j<9;j++) if(st[s][j]<st[s][i]) cnt++;
        code += fact[8-i] * cnt ;
    }
    if(vis[code]) return 0;
    vis[code]=1;
    return 1;
}
const int dx[]={0,0,1,-1};
const int dy[]={1,-1,0,0};
int dfs(){
     init();
     int front = 1 , rear = 2;
     while( front < rear ){
           state &s = st[front];
           if(memcmp(s,goal,sizeof(goal))==0) return front ;
           int z ;
           for(z=0;z<9;z++) if(!s[z]) break;
           int x=z/3;
           int y=z%3;
           for(int d=0;d<4;d++){
            int newx=x+dx[d];
            int newy=y+dy[d];
            int newz=newx*3+newy;
            if(newx>=0 && newx<3 &&newy>=0 && newy <3){
                state &t=st[rear];
                memcpy(&t,&s,sizeof(s));
                t[newz]=s[z];
                t[z]=s[newz];
                dist[rear]=dist[front]+1;
                if(try_to_insert(rear)) rear++;
            }
         }
         front++;
     }
}
int main(void){
    char s1[10],s2[10];
    scanf("%s%s",s1,s2);
    for(int i=0;i<9;i++){
         if(s1[i]!='.') st[1][i]=s1[i]-'0';  else st[1][i]=0;
         if(s2[i]!='.') goal[i]=s2[i]-'0'; else goal[i]=0;
    }
    int ans=dfs();
    if(ans) printf("%d\n",dist[ans]);
    else printf("%d\n",-1);
    return 0;
}

解题思路:





注意事项:





参考代码: