本题有写法好几个写法，但主要思路是BFS：
No。1 采用双向宽搜，分别从起始态和结束态进行宽搜，暴力判重。如果只进行单向会超时。No。2
采用hash进行判重，宽搜采用单向就可以AC。No。3
运用康拓展开进行判重，即使采用单向宽搜时间效率也很高。哈希是想到了，但是我们应该选择什么哈希函数呢，看了网上一些神牛利用的是"康托展开",也就是利用全排列都有一个对应的整数，利用哈希函数把状态压缩成整数，这样就可以做到每一个整数都是唯一对应一个状态，那么这个时候就把哈希做完了。
EightTime Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 29838 Accepted Submission(s): 7831Special JudgeProblem DescriptionThe 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 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 1213 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. InputYou 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 OutputYou 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 Input2 3 4 1 5 x 7 6 8 Sample Outputullddrurdllurdruldr SourceSouth Central USA 1998 (Sepcial Judge Module By JGShining)
【代码】:
#include#include #include #include #include #include #include #include #include #include #include
//思路： 单向bfs()+哈希判重+路径输出(由于POJ数据只有一组，这个方法可以在POJ上面A，其它oj不能A )#include#include #include #include #include #include #include #include #include #include using namespace std;#define MAXN 400000 struct State{ int state[9]; int pos;//空格位置 char ch[50];//记录原始状态到达当前状态的路径(数组不能开太大不然超内存)}s[MAXN];//每一个状态对应一个结构体int factor[9] = {1,1,2,6,24,120,720,5040,40320};//阶乘数组int dir[4][2] = { {-1,0},{0,1},{1,0},{0,-1}};//方向数组char dirtion[4] = {'u' , 'r' , 'd' , 'l'};int vis[MAXN];//标记某个状态是否被走过int start;//保存原始输入状态的哈希值State star;//原始状态对应的结构体queue q;//这里不能直接放结构体，不然肯定超时 //哈希映射int Hash(int s[]){ int i , j , temp , num; num = 0 ; for(i = 0 ; i < 9 ; i++){ temp = 0; for(j = i+1 ; j < 9 ; j++){ if(s[j] < s[i]) temp++; } num += factor[8-i]*temp; } return num; } //广搜bool Bfs(){ while(!q.empty()) q.pop(); memset(vis , 0 , sizeof(vis)); start = Hash(star.state); vis[start] = 1; s[start] = star; q.push(start); while(!q.empty()){ State cur = s[q.front()]; q.pop(); int x , y , r , c; x = cur.pos/3 ; y = cur.pos%3; for(int i = 0 ; i < 4 ; i++){ r = x+dir[i][0] ; c = y+dir[i][1]; if(r < 0 || c < 0 || r >= 3 || c >= 3) continue; State tmp = cur; tmp.state[tmp.pos] = tmp.state[3*r+c];//原先空格位置换成新的编号 tmp.pos = 3*r+c ; tmp.state[tmp.pos] = 9;//重新更新空格位置 int hash = Hash(tmp.state);//求出当前哈希值 if(vis[hash]) continue; vis[hash] = 1; int len = strlen(cur.ch);//求出前一个状态的路径长度 tmp.ch[len] = dirtion[i];//更新路径 s[hash] = tmp;//赋值 if(hash == 0){//如果搜索到目标节点直接输出退出 printf("%s\n" , s[hash].ch) ; return 1; } q.push(hash);//入对列 } } return 0;} int main(){ char c; while(scanf("%c" , &c) != EOF){ if(c == 'x'){ star.state[0] = 9 ; star.pos = 0;} else star.state[0] = c-'0'; for(int i = 1 ; i < 9 ; i++){ scanf(" %c" , &c); if(c == 'x'){ star.pos = i ; star.state[i] = 9;} else star.state[i] = c-'0'; } getchar(); int flag = Bfs(); if(!flag) printf("unsolvable\n");//无解的情况 } return 0;}