[ZJOI2005]九数码游戏

题目描述

输入输出格式

输入格式：

输入文件中包含三行三列九个数，同行的相邻两数用空格隔开，表示初始状态每个方格上的数字。初始状态不会是目标状态。

输出格式：

如果目标状态无法达到，则输出“UNSOLVABLE”（引号不输出）。

否则，第一行是一个整数S，表示最少的操作次数。接下来4 × (S + 1)行，每四行表示一个状态：前三行每行三个整数，相邻两数用空格隔开，表示每个方格上的数字，第四行是一个空行，作为分隔。第一个状态必须是初始状态，最后一个状态必须是目标状态。

输入输出样例

输入样例#1：

输出样例#1：

4

2 3 0

1 8 7

5 4 6

1 2 3

5 8 0

4 6 7

1 2 3

0 5 8

4 6 7

0 1 2

4 5 3

6 7 8

0 1 2

3 4 5

6 7 8

因为这是3*3的全排列矩阵变换；
最多有9！（362880）种状态；
用BFS，搜到终点为止，中间记录一下路径；
将3*3的全排列映射成一一对应的数，可以用康托展开；
最好不要用map，可能会超时；

#include<iostream>

#include<algorithm>

#include<cstdio>

#include<cstring>

#include<map>

using namespace std;  

int a[],q[],st,ed,b[],f[],ge,ans;

int c[],hash[];

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

int calc1()

{

    int i,j,t,sum;

    sum=;

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

    {

        t=;

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

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

                ++t;

        sum+=t*fac[-i-];

    }

    return sum+;

}  

int calc()

{

    int i,j,t,sum;

    sum=;

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

    {

        t=;

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

            if(b[i]>b[j])

                ++t;

        sum+=t*fac[-i-];

    }

    return sum+;

}  

void fen(int x)

{

    int i,j,t,vst[]={};

    x--;

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

    {

        t=x/fac[-i-];

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

            if(!vst[j])

            {

                if(t==) break;

                --t;

            }

        b[i]=j;

        vst[j]=;

        x%=fac[-i-];

    }

}  

int main()

{

    int x=;

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

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

            scanf("%d",&a[(i-)*+j-]);

        }

    x=calc1();

    ge=;

    if(x==ge){

        printf("");

        return ;

    }

    q[]=x;

    hash[x]=-;

    st=; ed=;

    while(st<ed){

        int x=q[++st];

        fen(x);

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

            f[i]=b[i];

        b[]=f[];

        b[]=f[];

        b[]=f[];

        int y=calc();

        if(hash[y]==){

            hash[y]=x;

            ed++;

            q[ed]=y;

        }

        if(y==ge)

            break;

        b[]=f[];

        b[]=f[];

        b[]=f[];

        b[]=f[];

        b[]=f[];

        b[]=f[];

        b[]=f[];

        b[]=f[];

        b[]=f[];

        b[]=f[];

        b[]=f[];

        y=calc();

        if(hash[y]==){

            hash[y]=x;

            ed++;

            q[ed]=y;

        }

        if(y==ge)

            break;

    }

    x=hash[ge];

    if(x==){

        printf("UNSOLVABLE\n");

        return ;

    }

    while(x!=-){

        ans++;

        c[ans]=x;

        x=hash[x];

    }

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

    for(int i=ans;i>;i--){

        fen(c[i]);

        printf("%d %d %d\n",b[],b[],b[]);

        printf("%d %d %d\n",b[],b[],b[]);

        printf("%d %d %d\n",b[],b[],b[]);

        printf("\n");

    }

    if(ans>=){

        printf("0 1 2\n");

        printf("3 4 5\n");

        printf("6 7 8\n");

    }

}

巴特西

[ZJOI2005]九数码游戏

[ZJOI2005]九数码游戏

题目描述

输入输出格式

输入输出样例

最新文章

热门文章