蓝桥杯 历届试题 九宫重排 （bfs+康托展开去重优化）

Description

如下面第一个图的九宫格中，放着 1~8 的数字卡片，还有一个格子空着。与空格子相邻的格子中的卡片可以移动到空格中。经过若干次移动，可以形成第二个图所示的局面。

我们把第一个图的局面记为：12345678.
把第二个图的局面记为：123.46758
显然是按从上到下，从左到右的顺序记录数字，空格记为句点。
本题目的任务是已知九宫的初态和终态，求最少经过多少步的移动可以到达。如果无论多少步都无法到达，则输出-1。

Input

输入第一行包含九宫的初态，第二行包含九宫的终态。

Output

输出最少的步数，如果不存在方案，则输出-1。

Sample Input

样例输入1

12345678.

123.46758

样例输入2

13524678.

46758123.

Sample Output

样例输出1

3

样例输出2

22

Source

蓝桥杯

 

分析：暴力bfs会超时

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

#define INF 99999999

#define me(a,x) memset(a,x,sizeof(a))

int mon1[]= {,,,,,,,,,,,,};

int mon2[]= {,,,,,,,,,,,,};

int dir[][]= {{,},{,-},{,},{-,}};

int fac[] = {, , , , , , , , , };//i的阶乘

LL getval()

{

    LL ret();

    char c;

    while((c=getchar())==' '||c=='\n'||c=='\r');

    ret=c-'';

    while((c=getchar())!=' '&&c!='\n'&&c!='\r')

        ret=ret*+c-'';

    return ret;

}

void out(int a)

{

    if(a>)

        out(a/);

    putchar(a%+'');

}

int kt(int a[],int n)//康托展开

{

    int ans=;

    for(int i=;i<=n;i++)

    {

        int c=;

        for(int j=i+;j<=n;j++)

        {

            if(a[j]<a[i])

                c++;

        }

        ans+=(c*fac[n-i]);

    }

    return ans+;

}

char str1[],str2[];

int a[][],b[][];

int sx,sy;

int t[];

int h;

int w;

bool vis[];

struct node

{

    int x,y,step;//x,y代表空格位置

    int c[][];//九宫格数组

    node(int xx,int yy,int ss,int cc[][])//初始化

    {

        x=xx;

        y=yy;

        step=ss;

        for(int i=; i<=; i++)

            for(int j=; j<=; j++)

                c[i][j]=cc[i][j];

    }

    int getkt()//得到结点数组的康托展开值

    {

        h=;

        for(int i=;i<=;i++)

        {

            for(int j=;j<=;j++)

            {

                t[h++]=c[i][j];

            }

        }

        return kt(t,);

    }

};

void init()//初始化

{

    int cnt=;

    for(int i=; i<=; i++)//得到原始九宫格

    {

        for(int j=; j<=; j++)

        {

            if(str1[cnt]=='.')

                a[i][j]=,sx=i,sy=j;

            else

                a[i][j]=str1[cnt]-'';

            cnt++;

        }

    }

    cnt=;

    for(int i=; i<=; i++)//得到目标九宫格

    {

        for(int j=; j<=; j++)

        {

            if(str2[cnt]=='.')

                b[i][j]=;

            else

                b[i][j]=str2[cnt]-'';

            cnt++;

        }

    }

    me(vis,false);//九宫格状态数组

    h=;

    for(int i=;i<=;i++)//得到目标九宫格的康托展开值

    {

        for(int j=;j<=;j++)

        {

            t[h++]=b[i][j];

        }

    }

    w=kt(t,);

}

int check(int x,int y)//边界约束

{

    if(x<=&&x>=&&y<=&&y>=)

        return ;

    return ;

}

int bfs(int x,int y,int a[][])

{

    queue<node> q;

    q.push(node(x,y,,a));

    vis[node(x,y,,a).getkt()]=;

    while(!q.empty())

    {

        int x=q.front().x;

        int y=q.front().y;

        int step=q.front().step;

        int c[][];

        for(int i=; i<=; i++)

            for(int j=; j<=; j++)

                c[i][j]=q.front().c[i][j];

        q.pop();

        for(int i=; i<; i++)

        {

            int xx=x+dir[i][];

            int yy=y+dir[i][];

            int ss=step+;

            int cc[][];

            if(check(xx,yy)==)//越界

                continue;

            for(int i=; i<=; i++)

                for(int j=; j<=; j++)

                    cc[i][j]=c[i][j];

            cc[x][y]=cc[xx][yy];//移动

            cc[xx][yy]=;

            if(vis[node(xx,yy,ss,cc).getkt()]==)//判断该状态的九宫格有没有搜索过

            {

                if(node(xx,yy,ss,cc).getkt()==w)//搜索到了目标

                {

                    return ss;//返回步数

                }

                int temp=node(xx,yy,ss,cc).getkt();

                vis[temp]=;//标记该状态的九宫格已经搜索过

                q.push(node(xx,yy,ss,cc));

            }

        }

    }

    return -;

}

int main()

{

    while(~scanf("%s",str1))

    {

        scanf("%s",str2);

        init();

        int ans=bfs(sx,sy,a);

        printf("%d\n",ans);

    }

}