Eight
Time Limit: 1000MS | Memory Limit: 65536K | |||
Total Submissions: 30127 | Accepted: 13108 | Special Judge |
Description
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
1 2 3
x 4 6
7 5 8
is described by this list:
1 2 3 x 4 6 7 5 8
Output
Sample Input
2 3 4 1 5 x 7 6 8
Sample Output
ullddrurdllurdruldr
//2016.8.25
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map> using namespace std; int a[][], b[], d[], sx, sy, deep;
bool ok;
map<int, bool> vis;
char dir[] = {'u', 'd', 'l', 'r'};
int dx[] = {-, , , };//分别对应上下左右四个方向
int dy[] = {, , -, }; bool solve()//求逆序对判断是否有解,偶数有解,奇数无解
{
int cnt = ;
for(int i = ; i <= ; i++)
for(int j = ; j < i; j++)
if(b[i] && b[j]>b[i])
cnt++;
return !(cnt%);
} int Astar()//启发函数,假设每个数字可以从别的数字头上跨过去,计算到达自己应该到的位置所需要的步数,即计算该数到达其正确位置的曼哈顿距离,h为各点曼哈顿距离之和
{
int h = ;
for(int i = ; i <= ; i++)
for(int j = ; j <= ; j++)
if(a[i][j]!=)
{
int nx = (a[i][j]-)/;
int ny = (a[i][j]-)%;
h += (abs(i-nx-)+abs(j-ny-));
}
return h;
} int toInt()//把矩阵转换为int型数字
{
int res = ;
for(int i = ; i <= ; i++)
for(int j = ; j <= ; j++)
res = res*+a[i][j];
return res;
} void IDAstar(int x, int y, int step)
{
if(ok)return ;
int h = Astar();
if(!h && toInt()==)//找到答案
{
for(int i = ; i < step; i++)
cout<<dir[d[i]];
cout<<endl;
ok = ;
return ;
}
if(step+h>deep)return ;//现实+理想<现状,则返回,IDA*最重要的剪枝
int now = toInt();
if(vis[now])return ;//如果状态已经搜过了,剪枝,避免重复搜索
vis[now] = true;
for(int i = ; i < ; i++)
{
int nx = x+dx[i];
int ny = y+dy[i];
if(nx>=&&nx<=&&ny>=&&ny<=)
{
d[step] = i;
swap(a[x][y], a[nx][ny]);
IDAstar(nx, ny, step+);
swap(a[x][y], a[nx][ny]);
d[step] = ;
}
}
return;
} int main()
{
char ch;
while(cin >> ch)
{
ok = false;
deep = ;
int cnt = ;
for(int i = ; i <= ; i++)
{
for(int j = ; j <= ; j++)
{
if(i==&&j==);
else cin >> ch;
if(ch == 'x')
{
a[i][j] = ;
sx = i;
sy = j;
}else
a[i][j] = ch - '';
b[cnt++] = a[i][j];
}
}
if(!solve())
{
cout<<"unsolvable"<<endl;
continue;
}
while(!ok)
{
vis.clear();
IDAstar(sx, sy, );
deep++;//一层一层增加搜索的深度
}
} return ;
}