Eight

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 28459    Accepted Submission(s): 7557Special 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 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 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.   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   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

这是一道经典的搜索题，在网上一搜一大把的解析……然鹅，一开始我只是想做道简单的BFS练练手先……没想到这道题如此“经典”，直接刚了一整天……下面开始我的总结。（新手向） 在做这道题之前，首先你得有预备知识，才能做出这道题。（康托展开/双向BFS/A*/逆序数奇偶性，怎么着你也得会一种，康托展开必备） 很明显这是一道搜索题。那么采用深搜还是宽搜呢？这个很显然不能用深搜。交换两个数，深搜可以深到天际，量太大了。而宽搜可以更快地遍历到所有的状态。我们的目标就是把所有的362880种状态都找出来，这点宽搜的缺点反而变成了优点。

好，我们得出结论，用宽搜。然后你会萌萌地发现，终止条件是啥啊？？呵呵，这时候我们悄悄看一眼DISCUSS，发现一个词“康托展开”。事实上，这道题不是用宽搜搜出答案来的。我们只是用宽搜去打表。我们会发现，所有的状态一共只有9！个，其实是有限的。而每个状态到达目标状态的方式都是唯一的。（这么说不太准确，其实方式可能有多种，但是对于某一种特点的解题策略而言，得出的结论应该是一样的。）所以说，思路来了：如果我们能求出那9！种状态各自的方法，那么只要把它存起来，输入哪种状态就输出答案就好了，绝对省时。 当然，萌新全凭自己写出代码还是不容易的。先看懂别人写的才是王道。

这里贴上代码，暂时只有一种，单向BFS+康托打表，我认为还是比较好理解的：

import java.util.Scanner; import java.util.LinkedList; public class Main { static int[] fac={1,1,2,6,24,120,720,5040,40320,362880}; static NodeWay[] nn=new NodeWay[363000]; static int[][] dir={{0,1},{1,0},{-1,0},{0,-1}}; public static void main(String[] args) { // TODO 自动生成的方法存根 Scanner cin=new Scanner(System.in); for(int i=0;i<nn.length;i++) { nn[i]=new NodeWay(); nn[i].Father=-1; } bfs(); while(cin.hasNext()) { int[] cc=new int[9]; int count=0; String str=cin.nextLine(); for(int i=0;i<str.length();i++) { if(str.charAt(i)==' ')continue; if(str.charAt(i)=='x'){ cc[count++]=0; }else{ cc[count++]=Integer.valueOf(str.charAt(i)+""); } } int cantorr=cantor(cc,9); if(nn[cantorr].Father==-1)System.out.println("unsolvable"); else{ while(nn[cantorr].Father!=0) { System.out.print(nn[cantorr].Way); cantorr=nn[cantorr].Father; } System.out.println(); } } } static int cantor(int[] number,int n) { int result=0; for(int i=0;i<n;i++) { int count=0; for(int j=i+1;j<n;j++) { if(number[i]>number[j])count++; } result+=count*fac[n-i-1]; } return result+1; } static void bfs() //从123456780的末状态开始往之前的状态搜，搜出一种不同的就给他存起来 { Node start=new Node(); start.CantorValue=46234; for(int i=0;i<9;i++) { start.map[i]=(i+1)%9; } start.loc=8; nn[46234].Father=0; int row; int col; LinkedList<Node> queue=new LinkedList<Node>(); queue.add(start); while(!queue.isEmpty()) { Node node=queue.poll(); for(int i=0;i<4;i++) { row=node.loc/3+dir[i][0]; col=node.loc%3+dir[i][1]; if(row<0||col<0||row>=3||col>=3)continue; Node work=new Node(); work.CantorValue=node.CantorValue; work.loc=node.loc; for(int k=0;k<9;k++){ work.map[k]=node.map[k]; } work.loc=row*3+col; int temp=0; temp=work.map[node.loc]; work.map[node.loc]=work.map[work.loc]; work.map[work.loc]=temp; work.CantorValue=cantor(work.map,9); if(nn[work.CantorValue].Father==-1) { nn[work.CantorValue].Father=node.CantorValue; if(i==0)nn[work.CantorValue].Way='l'; if(i==1)nn[work.CantorValue].Way='u'; if(i==2)nn[work.CantorValue].Way='d'; if(i==3)nn[work.CantorValue].Way='r'; queue.offer(work); } } } } } class NodeWay { char Way; int Father; NodeWay(){} } class Node { int CantorValue; //康托值 int[] map=new int[9]; //当前状态。用一维数组表示。 int loc; //标记出x的位置，方便操作 Node(){} }