EightTime Limit: 10000/5000 MS (Java/Others)Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 13506Accepted Submission(s): 3855Special 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 1213 14 15 xwhere 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 41 2 3 41 2 3 41 2 3 4 5 6 7 85 6 7 85 6 7 85 6 7 8 9 x 10 129 10 x 129 10 11 129 10 11 1213 14 11 15 13 14 11 15 13 14 x 15 13 14 15 xr->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, andfrustrating 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 threearrangement.
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 puzzle1 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
不得不说，，人这一生，要不是不刷这题，简直不完整啊。附上大量资料.。要想做这题，，，得好好准备啊！！
A*算法入门：%20Translation%20-%20For%20beginners.html
本题详细解析请看：
康托展开请看：康托展开
八数码八大境界：八数码的八境界
哎。做的时候可是相当痛苦啊。
下面是我的代码：
#include <cstdio>#include <queue>#include <cstring>#include<algorithm>#include <string>#define MAX 3using namespace std ;struct Node{int map[MAX][MAX] ,hash;int f,g,h;int x,y;/*bool operator<(const Node &n)const{return f>n.f ;}*///下面比上面更快 bool operator<(const Node n1)const{//优先队列第一关键字为h,第二关键字为greturn h!=n1.h?h>n1.h:g>n1.g;}bool check(){if(x<0||y<0 || x>=MAX||y>=MAX){return false ;}return true ;}};const int HASH[9]={1,1,2,6,24,120,720,5040,40320}; //HASH的权值 const int dir[4][2]={1,0,-1,0,0,-1,0,1} ;int visited[400000] ;int pre[400000] ;int des = 322560 ;int getHash(Node n){int oth[MAX*4] , k = 0;for(int i = 0 ; i < MAX ; ++i){ for(int j = 0 ; j < MAX ; ++j){oth[k++] = n.map[i][j] ;}}int result = 0 ;for(int i = 0 ; i < 9 ; ++i){int count = 0 ; for(int j = 0 ; j < i ; ++j){if(oth[i]<oth[j]){count++;}}result += count*HASH[i] ;}return result ;}int getH(Node n){int result = 0 ;for(int i = 0 ; i < MAX ; ++i){for(int j = 0 ; j < MAX ; ++j){if(n.map[i][j]){int x = (n.map[i][j]-1)/3 , y = (n.map[i][j]-1)%3 ;result += abs(x-i)+abs(y-j) ;}}}return result ;}bool judge(Node n){int oth[MAX*4] , k = 0;for(int i = 0 ; i < MAX ; ++i){ for(int j = 0 ; j < MAX ; ++j){oth[k++] = n.map[i][j] ;}}int result = 0 ;for(int i = 0 ; i < 9 ; ++i){for(int j = i+1 ; j < 9 ; ++j){if(oth[i]&&oth[j]&&oth[i]>oth[j]){++result;}}}return !(result&1) ;}void AStar(Node start){priority_queue<Node> p;p.push(start);while(!p.empty()){Node n = p.top();p.pop();for(int i = 0 ; i < 4 ; ++i){Node next = n;next.x += dir[i][0];next.y += dir[i][1];if(!next.check()){continue ;}swap(next.map[next.x][next.y],next.map[n.x][n.y]) ;next.hash = getHash(next) ;if(visited[next.hash] == -1){next.h = getH(next) ;next.g++ ;next.f = next.g+next.h;pre[next.hash] = n.hash ;p.push(next) ;visited[next.hash] = i ;//i代表方向}if(next.hash == des){return ;}}}}void print(){int next = des ;string ans;ans.clear() ;while(pre[next]!=-1){switch(visited[next]){case 0 : ans += 'd' ; break ;case 1 : ans += 'u' ; break ;case 2 : ans += 'l' ; break ;case 3 : ans += 'r' ; break ;default : break ; }next = pre[next] ;}int len = ans.size() ;for(int i = len-1 ; i >=0 ; –i){putchar(ans[i]) ;}puts("");}int main(){char str[100] ;while(gets(str) != NULL){Node t ;memset(visited,-1,sizeof(visited)) ;memset(pre,-1,sizeof(pre)) ;int k = 0 ,i = 0;while(str[k] != '\0'){if(str[k]>'0'&&str[k]<='9'){t.map[i/3][i%3] = str[k]-'0' ;++i ;}else if(str[k] == 'x'){t.x = i/3 ;t.y = i%3 ;t.map[i/3][i%3] = 0 ;++i ;}++k ;}t.hash=getHash(t);visited[t.hash] = -2 ;t.g = 0 ;t.h = getH(t);t.f = t.g+t.h;if(!judge(t)){printf("unsolvable\n");continue ;}if(t.hash == des){puts("");continue ;}AStar(t) ;print();}return 0;}
人生并不在于获取，更在于放得下。放下一粒种子，收获一棵大树；
