http://acm.hdu.edu.cn/showproblem.php?pid=1043
http://poj.org/problem?id=1077
Eight
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 9173 Accepted Submission(s): 2473 Special Judge
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.
1 2 3
is described by this list:
1 2 3 x 4 6 7 5 8
{1,2,3,4,...,n}表示1,2,3,...,n的排列如 {1,2,3} 按从小到大排列一共6个。123 132 213 231 312 321 。
代表的数字 1 2 3 4 5 6 也就是把10进制数与一个排列对应起来。
他们间的对应关系可由康托展开来找到。
如我想知道321是{1,2,3}中第几个大的数可以这样考虑 ：
第一位是3，当第一位的数小于3时，那排列数小于321 如 123、 213 ，小于3的数有1、2 。所以有2*2!个。再看小于第二位2的：小于2的数只有一个就是1 ，
所以有1*1!=1 所以小于321的{1,2,3}排列数有2*2!+1*1!=5个。所以321是第6个大的数。 2*2!+1*1!+0*0!就是康托展开。
再举个例子：1324是{1,2,3,4}排列数中第几个大的数：第一位是1小于1的数没有，是0个 0*3! 第二位是3小于3的数有1和2，但1已经在第一位了，
所以只有一个数2 1*2! 。第三位是2小于2的数是1，但1在第一位，所以有0个数 0*1! ，所以比1324小的排列有0*3!+1*2!+0*1!=2个，1324是第三个大数。
#include <iostream>
#include <stdio.h>
#include <queue>
#include <string.h> using namespace std;
#define N 363000 struct Nod
{
int b[];
int x,y,pos;
}nd1,nd2; int fac[] = {,,,,,,,,,}; //康拓展开用到的数组
//康托展开：
int cantor(int* a, int k)
{
int i, j, tmp, num = ;
for (i = ; i < k; i++) {
tmp = ;
for (j = i + ; j < k; j++)
if (a[j] < a[i])
tmp++;
num += fac[k - i - ] * tmp;
}
return num;
} int mark[N],pre[N];
char dir[N];
int cx[]={,,,-};
int cy[]={-,,,}; void exchange(int *a,int x,int y)
{
int temp=a[x];
a[x]=a[y];
a[y]=temp;
} void bfs(int *b,int x,int y)
{
queue<Nod> q;
memset(mark,,sizeof(mark));
memset(pre,-,sizeof(pre));
nd1.x=x;
nd1.y=y;
memcpy(nd1.b,b,sizeof(int)*);
int i,temp;
temp = cantor(b,);
mark[temp] = ;
nd1.pos = temp;
q.push(nd1);
while(!q.empty())
{
nd2 = q.front();
q.pop();
for(i=;i<;i++)
{
nd1.x = nd2.x + cx[i];
nd1.y = nd2.y + cy[i];
if(nd1.x>=&&nd1.x<&&nd1.y>=&&nd1.y<)
{
memcpy(nd1.b,nd2.b,sizeof(int)*);
exchange(nd1.b,nd1.x*+nd1.y,nd2.x*+nd2.y);
temp = cantor(nd1.b,);
nd1.pos = temp;
if(mark[temp]==) continue;
mark[temp] = ;
pre[temp] = nd2.pos;
if(cx[i]==)
{
if(cy[i]==) dir[temp] = 'l'; //因为是从目标状态开始搜索的，最后需要倒序输出，然后方向也应该是相反输出
else dir[temp] = 'r'; //dir[temp] = 'l' 的反方向
}
if(cy[i]==)
{
if(cx[i]==) dir[temp] = 'u'; //同上
else dir[temp] = 'd'; //同上
}
q.push(nd1);
}
}
}
} int main()
{
char str[];
int a[],b[]={,,,,,,,,}; //末状态，从末状态开始搜索
bfs(b,,); //预先搜索所有状态
while(~scanf("%s",str))
{
if(str[]=='x') a[]=;
else a[]=str[]-'';
int i;
for(i=;i<;i++)
{
scanf("%s",str);
if(str[]=='x') a[i]=;
else a[i]=str[]-'';
}
int temp = cantor(a,); //得到起始状态，然后回溯到末状态
if(!mark[temp]) //所有状态里面若没有起始状态，则为不可达
{
printf("unsolvable\n");
continue;
}
while(temp) //回溯过程
{
printf("%c",dir[temp]);
temp = pre[temp];
}
putchar();
}
return ;
}