蓝桥杯的一道题。

我用了全排列的编码优化。

AC代码

#include
     
      #include
      
       const int maxn=400000;const int dx[]={-1,1,0,0};const int dy[]={
    0,0,-1,1};typedef int state[9];int goal[9];int res[maxn][9]; //存储访问过的节点 int d[maxn],fact[9];int vis[maxn];void init(){    fact[0]=1;    for(int i=1;i<9;++i)    fact[i]=i*fact[i-1];}int KT_solve(int row)  //编码函数 {    int code=0;    for(int i=0;i<9;++i)    {        int cnt=0;        for(int j=i+1;j<9;++j)        {            if(res[row][j]
       
        =0&&newy<3&&newy>=0&&newy<3)            {                state &t=res[real]; //向状态数组加入新的状态                 memcpy(&t,&s,sizeof(s));                t[pos]=s[new_pos];                t[new_pos]=s[pos];                d[real]=d[front]+1;                if(KT_solve(real)) real++;            }        }        front++;    }    return 0;}int main(){    memset(vis,0,sizeof(vis));    d[1]=0;    char s[10];    scanf("%s",s);    for(int j=0;j<9;++j)    {        if(s[j]=='.')        res[1][j]=0;        else res[1][j]=s[j]-'0';    }    scanf("%s",s);    for(int j=0;j<9;++j)    {        if(s[j]=='.')        goal[j]=0;        else goal[j]=s[j]-'0';    }    int ans=bfs();    if(ans>0)    printf("%d\n",d[ans]);    else printf("-1\n");    return 0;}
       
      
     

如有不当之处欢迎指出！