[ZJOI2005]九数码游戏-白红宇

[ZJOI2005]九数码游戏

阅读量：5241 次

发布时间：2019-06-14

本文共 2080 字，大约阅读时间需要 6 分钟。

[ZJOI2005]九数码游戏

题目描述

输入输出格式

输入格式：

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

输出格式：

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

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

输入输出样例

输入样例#1：

2 3 01 8 75 4 6

输出样例#1：

42 3 01 8 75 4 61 2 35 8 04 6 71 2 30 5 84 6 70 1 24 5 36 7 80 1 23 4 56 7 8 因为这是3*3的全排列矩阵变换； 最多有9！（362880）种状态； 用BFS，搜到终点为止，中间记录一下路径； 将3*3的全排列映射成一一对应的数，可以用康托展开； 最好不要用map，可能会超时；

#include
       
          #include
        
         #include
         
          #include
          
           #include
             using namespace std;  int a[9],q[400008],st,ed,b[9],f[9],ge,ans;int c[400008],hash[400008];int  fac[10]={
     1,1,2,6,24,120,720,5040,40320}; int calc1()  {      int i,j,t,sum;      sum=0;      for(i=0;i<9;i++)      {          t=0;          for(j=i+1;j<9;j++)              if(a[i]>a[j])                  ++t;          sum+=t*fac[9-i-1];      }      return sum+1;  }  int calc()  {      int i,j,t,sum;      sum=0;      for(i=0;i<9;i++)      {          t=0;          for(j=i+1;j<9;j++)              if(b[i]>b[j])                  ++t;          sum+=t*fac[9-i-1];      }      return sum+1;  }  void fen(int x)  {       int i,j,t,vst[9]={
     0};    x--;     for(i=0;i<9;i++)      {          t=x/fac[9-i-1];          for(j=0;j<9;j++)              if(!vst[j])              {                if(t==0) break;                  --t;              }        b[i]=j;        vst[j]=1;        x%=fac[9-i-1];    }  }  int main()  {      int x=0;    for(int i=1;i<=3;i++)        for(int j=1;j<=3;j++){            scanf("%d",&a[(i-1)*3+j-1]);        }    x=calc1();    ge=1;    if(x==ge){        printf("0");        return 0;    }    q[1]=x;    hash[x]=-1;    st=0; ed=1;    while(st
            
             0;i--){ fen(c[i]); printf("%d %d %d\n",b[0],b[1],b[2]); printf("%d %d %d\n",b[3],b[4],b[5]); printf("%d %d %d\n",b[6],b[7],b[8]); printf("\n"); } if(ans>=1){ printf("0 1 2\n"); printf("3 4 5\n"); printf("6 7 8\n"); }}

转载于:https://www.cnblogs.com/WQHui/p/7677338.html

你可能感兴趣的文章