题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1043
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.
题意描述：给出一个3×3的矩阵（包含1～8数字和一个字母x），经过一些移动格子上的数后得到连续的1～8，最后一格是x，要求最小移动步数。
算法分析：经典的八数码问题。八数码属于搜索方面的问题，经典解法有bfs、A*、IDA*等等。网上资料很多，这里简单介绍一下A*。
A*：f=g+h函数。g表示从起点到当前点的移动步数，h表示对当前点到目标点的最小移动步数的预测。除去起点和目标点，我们走在任意一点上的时候，下一步很容易想到应该选择f较小的继续。（对于h的计算我们可以用曼哈顿距离公式）
康托展开：这道题里面的作用在于实施hash函数，对于当前这一步后得到一个新的矩阵，用康托展开公式计算这个矩阵的hash值，用在宽搜时判断。
还有一点优化的地方：判断当前矩阵是否可以达到目标矩阵（矩阵里两个数实施交换后，逆序数的奇偶性和目标矩阵一致才可以有机会达到目标矩阵）
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#define inf 0x7fffffff
using namespace std;
const int maxn=;
const int M = +; struct node
{
int mase[][];
int x,y;
int f,g,h;
int flag;
friend bool operator < (node a,node b)
{
return a.f > b.f;
}
}start,tail;
int pre[M],v[M]; char str[]={'u','d','l','r' };
int Can[]={,,,,,,,, };
const int destination=;
int Cantor(node cur) ///康托展开
{
int an[],k=;
for (int i= ;i< ;i++)
for (int j= ;j< ;j++)
an[k++]=cur.mase[i][j];
int sum=;
for (int i= ;i< ;i++)
{
int k=;
for (int j=i+ ;j< ;j++)
if (an[i]>an[j]) k++;
sum += k*Can[-i-];
}
return sum+;
} int is_ok(node an) ///判断此时奇偶性
{
int a[],k=;
for (int i= ;i< ;i++)
for (int j= ;j< ;j++)
a[k++]=an.mase[i][j];
int sum=;
for (int i= ;i<k ;i++) if (a[i]!=)
for (int j= ;j<i ;j++)
if (a[j]!= && a[j]>a[i]) sum ++ ;
if (sum&) return ;
return ;
} void print(node cur)
{
string ans;
int sum=destination;
while (pre[sum] != -)
{
switch (v[sum]) {
case : ans += str[];break;
case : ans += str[];break;
case : ans += str[];break;
case : ans += str[];break;
}
sum=pre[sum];
}
int len=ans.size() ;
for (int i=len- ;i>= ;i--) putchar(ans[i]);
return ;
} pair<int,int> pii[];
int getH(node cur)
{
int r=,c=;
for (int i= ;i<= ;i++)
{
pii[i%].first=r ;
pii[i%].second=c;
c++;
if (c==) {r++;c=; }
}
int sum=;
for (int i= ;i< ;i++)
{
for (int j= ;j< ;j++)
{
int u=cur.mase[i][j];
sum += abs(pii[u].first-i)+abs(pii[u].second-j);
}
}
return sum;
} int vis[M];
int an[][]={-,, ,, ,-, , };
void A_star(node cur)
{
priority_queue<node> Q;
cur.g= ;cur.h=getH(cur);
cur.f=cur.g + cur.h ;
cur.flag=-;
Q.push(cur);
memset(vis,-,sizeof(vis));
memset(pre,-,sizeof(pre));
memset(v,-,sizeof(v));
vis[Cantor(cur) ]=;
while (!Q.empty())
{
cur=Q.top() ;Q.pop() ;
if (Cantor(cur)==destination)
{
// cout<<cur.g<<endl;
// for (int i=0 ;i<3 ;i++)
// {
// for (int j=0 ;j<3 ;j++)
// cout<<cur.mase[i][j]<<" ";
// cout<<endl;
// }
///输出序列
print(cur);
return ;
}
for (int i= ;i< ;i++)
{
tail.x=cur.x+an[i][];
tail.y=cur.y+an[i][];
int x=cur.x ,y=cur.y ;
for (int u= ;u< ;u++)
for (int v= ;v< ;v++)
tail.mase[u][v]=cur.mase[u][v];
if (tail.x<||tail.x>=||tail.y<||tail.y>=) continue;
swap(tail.mase[tail.x][tail.y],tail.mase[x][y]);
int sum=Cantor(tail);
if (vis[sum]==-)
{
if (is_ok(tail)==) continue;
vis[sum]=;
tail.g=cur.g+;
tail.h=getH(tail);
tail.f=tail.g+tail.h;
if (tail.x==x+) tail.flag=;
else if (tail.x==x-) tail.flag=;
else if (tail.y==y-) tail.flag=;
else if (tail.y==y+) tail.flag=;
pre[sum]=Cantor(cur);
v[sum]=i;
Q.push(tail);
}
}
}
return ;
} int main()
{
char str[];
while (gets(str))
{
int r=,c=;
int len=strlen(str);
int ok=;
for (int i= ;i<len ;i++)
{
if (str[i]>='' && str[i]<='')
{
start.mase[r][c]=str[i]-'';
c++;
if (c==) {r++;c=; }
}
else if (str[i]=='x')
{
start.mase[r][c]=;
start.x=r ;start.y=c ;
c++;
if (c==) {r++;c=; }
}
}
int sum=Cantor(start);
if (sum==destination) {printf("\n");continue; }
if (is_ok(start)==) {printf("unsolvable\n");continue; }
A_star(start);
printf("\n");
}
return ;
}