Eight
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 13956 Accepted Submission(s): 3957 Special Judge
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
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
2 3 4 1 5 x 7 6 8
Sample Output
ullddrurdllurdruldr
这题活生生搞了五天，为此学了A*和康托展开，虽然自己写出来了但还不是非常明白，有句话说“如果你真的懂了那么你就应该自己动手做一个”，看来我还没真的懂。
首先把每次矩阵的格局存结构里，然后对整个矩阵用康托展开来进行哈希，得到一个值，以此来判断此种情况是否出现过或是是否到达了终点，有一个很好的剪枝就是用奇偶逆序数来判断是否可解，因为最终情况的逆序数是0，而每次变换不会改变逆序数的奇偶，所以如果初始情况的逆序数是奇数的话就不可解。
不明白的地方是A*的估值函数为何不用f = g + h，而是要用h和g分别作为两个参数来比较，刚开始的时候我把两个参数的位置弄反了， T了一天。都是泪。
#include <iostream>
#include <cmath>
#include <string>
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; const int SIZE = ;
const int GOAL = ;
const int HASH[] = {,,,,,,,,};
const int UP_DATE[][] = {{,-},{,},{-,},{,}};
int PATH[];
int PRE[];
struct Node
{
int map[SIZE][SIZE];
int x,y;
int h,g;
int hash;
bool operator <(const Node a) const
{
return h != a.h ? h > a.h : g > a.g;
}
}; bool solve_able(const Node & r);
bool check(const int,const int);
void cal_hash(Node & r);
void cal_h(Node & r);
void search(const Node & r);
void show(void);
int main(void)
{
Node first;
char s[]; while(gets(s))
{
int k = ;
memset(PRE,-,sizeof(PRE));
memset(PATH,-,sizeof(PATH));
for(int i = ;i <= ;i ++)
for(int j = ;j <= ;j ++)
{
if(s[k] >= '' && s[k] <= '')
first.map[i][j] = s[k] - '';
else if(s[k] == 'x')
{
first.map[i][j] = ;
first.x = i;
first.y = j;
}
else
j --;
k ++;
}
if(!solve_able(first))
{
printf("unsolvable\n");
continue;
}
cal_hash(first);
if(first.hash == GOAL)
{
puts("");
continue;
}
PATH[first.hash] = -;
first.g = ;
cal_h(first);
search(first);
} return ;
} bool solve_able(const Node & r)
{
int sum = ,count = ;
int temp[]; for(int i = ;i <= ;i ++)
for(int j = ;j <= ;j ++)
{
temp[count] = r.map[i][j];
count ++;
}
for(int i = ;i < ;i ++)
for(int j = i + ;j < ;j ++)
if(temp[j] < temp[i] && temp[j] && temp[i])
sum ++;
return !(sum & );
} bool check(const int x,const int y)
{
if(x >= && x <= && y >= && y <= )
return true;
return false;
} void cal_hash(Node & r)
{
int sum = ,count = ,box;
int temp[]; for(int i = ;i <= ;i ++)
for(int j = ;j <= ;j ++)
{
temp[count] = r.map[i][j];
count ++;
}
for(int i = ;i < ;i ++)
{
box = ;
for(int j = i + ;j < ;j ++)
if(temp[j] < temp[i])
box ++;
sum += (box * HASH[i]);
}
r.hash = sum;
} void search(Node const & r)
{
Node cur,next; priority_queue<Node> que;
que.push(r);
while(!que.empty())
{
cur = que.top();
que.pop();
for(int i = ;i < ;i ++)
{
next = cur;
next.x = cur.x + UP_DATE[i][];
next.y = cur.y + UP_DATE[i][];
if(!check(next.x,next.y))
continue;
swap(next.map[cur.x][cur.y],next.map[next.x][next.y]);
cal_hash(next); if(PATH[next.hash] == -)
{
PATH[next.hash] = i;
PRE[next.hash] = cur.hash;
next.g ++;
cal_h(next);
que.push(next);
}
if(next.hash == GOAL)
{
show();
return ;
}
}
} } void cal_h(Node & r)
{
int ans = ;
for(int i = ;i <= ;i ++)
for(int j = ;j <= ;j ++)
if(r.map[i][j])
ans += abs(i - ((r.map[i][j] - ) / + )) + abs(j - ((r.map[i][j] - ) % + ));
r.h = ans;
} void show(void)
{
string ans;
int hash = GOAL; ans.clear();
while(PRE[hash] != -)
{
switch(PATH[hash])
{
case :ans += 'l';break;
case :ans += 'r';break;
case :ans += 'u';break;
case :ans += 'd';break;
}
hash = PRE[hash];
}
for(int i = ans.size() - ;i >= ;i --)
printf("%c",ans[i]);
cout << endl;
}