Problem Description

The 15-puzzle has been around for over 100 years; even if you don‘t know it by that name, you‘ve seen it. It is constructed with 15 sliding tiles, each with a number from 1 to 15 on it, and all packed into a 4 by 4 frame with one tile missing. Let‘s call the missing tile ‘x‘; the object of the puzzle is to arrange the tiles so that they are ordered as:

 1  2  3  4
 5  6  7  8
 9 10 11 12
13 14 15  x

where the only legal operation is to exchange ‘x‘ with one of the tiles with which it shares an edge. As an example, the following sequence of moves solves a slightly scrambled puzzle:

 1  2  3  4     1  2  3  4     1  2  3  4     1  2  3  4
 5  6  7  8     5  6  7  8     5  6  7  8     5  6  7  8
 9  x 10 12     9 10  x 12     9 10 11 12     9 10 11 12
13 14 11 15    13 14 11 15    13 14  x 15    13 14 15  x
            r->            d->            r->

The letters in the previous row indicate which neighbor of the ‘x‘ tile is swapped with the ‘x‘ tile at each step; legal values are ‘r‘,‘l‘,‘u‘ and ‘d‘, for right, left, up, and down, respectively.

Not all puzzles can be solved; in 1870, a man named Sam Loyd was famous for distributing an unsolvable version of the puzzle, and
frustrating many people. In fact, all you have to do to make a regular puzzle into an unsolvable one is to swap two tiles (not counting the missing ‘x‘ tile, of course).

In this problem, you will write a program for solving the less well-known 8-puzzle, composed of tiles on a three by three
arrangement.

 

Input

You will receive, several descriptions of configuration of the 8 puzzle. One description is just a list of the tiles in their initial positions, with the rows listed from top to bottom, and the tiles listed from left to right within a row, where the tiles are represented by numbers 1 to 8, plus ‘x‘. For example, this puzzle

1 2 3
x 4 6
7 5 8

is described by this list:

1 2 3 x 4 6 7 5 8

 

Output

You will print to standard output either the word ``unsolvable‘‘, if the puzzle has no solution, or a string consisting entirely of the letters ‘r‘, ‘l‘, ‘u‘ and ‘d‘ that describes a series of moves that produce a solution. The string should include no spaces and start at the beginning of the line. Do not print a blank line between cases.

 

Sample Input

 

Sample Output

 

Source

South Central USA 1998 (Sepcial Judge Module By JGShining)

 

Recommend

JGShining   |   We have carefully selected several similar problems for you:  1044 1026 1072 1010 1180 

题目大意:

给你一个3*3的方格，其中的值为1~8,x,然后你每次能将x与上下左右的四个格子里的元素对调，然后要求将方格里的值调成：

1 2 3

4 5 6

7 8 x

输出怎样变换能够得到（对应的x的l,r,u,p上下左右的移动过程）。对不能完成的情况输出unsolvable。

 

首先这道题我们先思考如何用一个数表示每个棋盘的状态。首先直接把x表示为0。

1.最容易想到的就是变成一个9进制数，但是要表示的数很大，所以并不可行

2.表示成这个数在n!中的排名，表示方法为康托展开。

rk1*(n-1)!+rk2*(n-2)!+...+rkn*0!

rki表示i在i+1..n中的排名

举例312

2*2!+0*1!+0*0!=4

原因其实这个阶段实在计算排列比这个排列字典序更靠前的有多少个，

对于第一位，后面如果有rki个比它小的，就可以知道以这些为开头的都比它小，后面的计算也是如此。

然而复杂度是n^2,这也许就是所谓的时空平衡吧。

然而如果我们在已经知道排名后应该怎么计算原本的排列呢？

有个很像10进制转二进制的想法。

rk1=z/(n-1)! z%=(n-1)!

rk2=z/(n-2)! z%=(n-2)!

...

rkn=z/0! z%=0!

然后就可以根据rk得到原本的序列了(0v0)

 

另一件事，并不是所有的序列都能转化为我们想要的那个，所以需要先进行判断。

而判断的方法是将0移动到与目标相同的0的位置上

然后求对于每一个i，前面比它小的有多少个，如果与目标的奇偶性不同的话，那么输出unsolvable即可

然后开始广搜，要注意判断重复，并且对于每个点记录上一层扩展来的点以便输出方案，然而tle，因为此题是多组数据，所以我们需要进行双向广搜。

过程:

建两个队列，把初始元素放入队列1，把目标元素放入队列2。

然后判断两个队列那一边元素更少，然后选择元素少的那个队列开始扩展。

然后如果新的节点，另一个队列已经走过就可以输出答案了。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=400000;
int x[10],jc[10],to[2][N];
bool yg[10];
struct Z
{
    int z,sg;
    char fx;
}q[2][N];
char bh[2][5]={"udlr","durl"},sr[105];
int has(int *a)
{
    int re=0;
    for(int i=1;i<=9;++i)
    {
        int s=0;
        for(int j=i+1;j<=9;++j)
            if(a[i]>a[j]) ++s;
        re+=s*jc[9-i];
    }
    return re;
}
void nihash(int z)
{
    memset(yg,0,sizeof(yg));
    for(int i=1;i<=9;++i) 
    {
        int rk=z/jc[9-i],k=0;
        z%=jc[9-i];
        for(int j=0;j<=rk;++k)
            if(!yg[k]) ++j;
        yg[x[i]=k-1]=1;
    }
}
int chan(int z,int xh)
{
    nihash(z);
    int wz;
    for(int i=1;i<=9;++i)
        if(!x[i])
        {
            wz=i;
            break;
        }
    switch (xh)
    {
        case 0:if(wz<4) return -1;
               swap(x[wz],x[wz-3]);
               break;
        case 1:if(wz>6) return -1;
               swap(x[wz],x[wz+3]);
               break;
        case 2:if(wz%3==1) return -1;
               swap(x[wz],x[wz-1]);
               break;
        case 3:if(wz%3==0) return -1;
               swap(x[wz],x[wz+1]);
               break;
    }
    return has(x);
}
void print(int a)
{
    if(a==1) return;
    print(q[0][a].sg);
    printf("%c",q[0][a].fx);
}
void bfs()
{
        
    int t[2]={1,1},w[2]={1,1};
    for(;t[0]<=w[0]&&t[1]<=w[1];)
    {
        int xh=w[1]-t[1]<w[0]-t[0];
        for(int i=0;i<4;++i)
        {
            int ns=chan(q[xh][t[xh]].z,i);
            if(ns!=-1&&!to[xh][ns])
            {
                q[xh][++w[xh]]=(Z){ns,t[xh],bh[xh][i]};
                to[xh][ns]=w[xh];
                if(to[!xh][ns])
                {
                    print(to[0][ns]);
                    for(int j=to[1][ns];j>1;j=q[1][j].sg) 
                        printf("%c",q[1][j].fx);
                    return;
                }
            }
        }
        ++t[xh];
    }
}
int main()
{
    jc[0]=1;
    for(int i=1;i<=9;++i) jc[i]=jc[i-1]*i;
    while(cin.getline(sr,100))
    {    
        memset(to,0,sizeof(to));
        int cw,lj=0,len=strlen(sr);
        for(int i=0,j=0;j<9;++i)
            if(sr[i]==‘x‘) x[cw=++j]=0;
            else if(sr[i]>=‘0‘&&sr[i]<=‘9‘) x[++j]=sr[i]-‘0‘;
        to[0][q[0][1].z=has(x)]=1;
        if(q[0][1].z==46233) 
        {    
            printf("\n");            
            continue;
        }
        to[1][q[1][1].z=46233]=1;
        while(cw!=9)
        if(cw<7) swap(x[cw],x[cw+3]),cw+=3;
        else swap(x[cw],x[cw+1]),++cw;
        for(int i=2;i<9;++i)
            for(int j=1;j<i;++j)
                if(x[j]<x[i]) ++lj;
        if(lj&1)
        {
            printf("unsolvable\n");
            continue;
        }
        bfs();printf("\n");
    }
    return 0;
}