历届试题九宫重排

http://sxnuwhui.blog.163.com/blog/static/13706837320125494648469/

小白书132页，我没弄明白 try_to_insert（）函数。

历届试题九宫重排

时间限制：1.0s 内存限制：256.0MB

问题描述

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

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

输入格式

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

输出格式

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

样例输入

12345678.
123.46758

样例输出

3

样例输入

13524678.
46758123.

样例输出

22

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
//typedef int State[9];
//State  st[10000000],goal;
char  str[10000000][10];
int st [1000000][10],goal[10];
char goa[10];
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
int dist[1000000];
int vis[362880], fact[9];//注意这里为什么要开362880大小，因为n!=∑i*i!(i从0到n-1)，9！=362879.
void init_lookup_table()
{
    memset(vis, 0, sizeof(vis));
    memset(fact, 0, sizeof(fact));
    fact[0] = 1;
    for(int i = 1; i < 9; i++)
        fact[i] = fact[i - 1] * i;
}
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;
    return vis[code] = 1;
}


int bfs()
{

    init_lookup_table();
   int front=1,rear=2;
    while(front<rear)
    {

        if(memcmp(goal,st[front],sizeof(st[front]))==0)
             return front;
        int z;
        for(z=0;z<9;z++)
           if(st[front][z]==0)
                break;
        int x=z/3,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)
              {

                   memcpy(st[rear],st[front], sizeof(st[front]));
                  st[rear][newz] = st[front][z];
                  st[rear][z] = st[front][newz];
                  dist[rear]=dist[front]+1;
                    if(try_to_insert(rear))
                    rear++;
             }
        }
        front++;
    }
    return 0;
}
int main()
{
    int i;
     memset(dist,0,sizeof(dist));
    scanf("%s",str[1]);
     scanf("%s",goa);
     int len1=strlen(str[1]);
    int len2=strlen(goa);
    for(i=0;i<len1;i++)
        {
            if(str[1][i]=='.')
                 st[1][i]=0;
            else
             st[1][i]=str[1][i]-'0';
        }
     //for(i=0;i<len1;i++)
       //     printf("%d ",st[1][i]);
   // printf("
");
     for(i=0;i<len2;i++)
        {
             if(goa[i]=='.')
                goa[i]=0;
            else
              goal[i]=goa[i]-'0';
        }
      //  for(i=0;i<len1;i++)
      //      printf("%d ",goal[i]);
 //   printf("
");
    int ans=bfs();
   if(ans>0)
        printf("%d
",dist[ans]);
   else
     printf("-1
");

    return 0;
}
/*
12345678.
123.46758
3
*/

历届试题 九宫重排

历届试题九宫重排