九宫重排—题解

import java.util.LinkedList;
import java.util.Scanner;



public class Asist
{
	public static final int fac[] = {1,1,2,6,24,120,720,5040,40320,362880};
	public static final int move[][] = {{1,0},{-1,0},{0,1},{0,-1}};
	public static final int MAX = 1000000;
	public static  int step = -1;
    
	public static void main(String[] args)
	{
		Scanner sc = new Scanner(System.in);
		String str1 = sc.nextLine();
		String str2 = sc.nextLine();
	    Node start = new Node();
	    Node end = new Node();
	    for (int i = 0; i < str1.length(); i++)
	    {
	    	if (str1.charAt(i) == '.')
	    	{
	    		start.s = new StringBuffer(str1);
	    		start.s.replace(i, i+1, "0");
	    		start.index = i;
	    		start.step = 0;
	    		start.status = getHash(start.s.toString(), 9);
	    	}
	    	if (str2.charAt(i) == '.')
	    	{
	    		end.s = new StringBuffer(str2);
	    		end.s.replace(i, i+1, "0");
	    		end.index = i;
	    		end.step = 0;
	    		end.status = getHash(end.s.toString(), 9);
	    	}
	    }
	    if (str1.equals(str2)) System.out.println(0);
	    else
	    {
	    	bfs(start, end);
	    	System.out.println(step);
	    }
	}

	private static void bfs(Node start, Node end)
	{
        boolean vis[] = new boolean[MAX];
        LinkedList<Node> list = new LinkedList<Node>();
        Node cur, next;
        cur = getNode(start);
        list.add(cur);
        
        while(!list.isEmpty())
        {
        	cur = list.pop();
            int x = cur.index / 3;
            int y = cur.index % 3;
            for (int i = 0; i < 4; i++)
            {
               int tx = x + move[i][0];
               int ty = y + move[i][1];
               if (tx > 2 || tx < 0 || ty > 2 || ty < 0) continue;
               next = getNode(cur);
               next.index = tx * 3 + ty;
               next.s.replace(cur.index, cur.index+1, cur.s.charAt(next.index)+"");
               next.s.replace(next.index, next.index+1, "0");
               next.step++;
               next.status = getHash(next.s.toString(), 9);
               
               if (next.status == end.status)
               {
            	   step = next.step; return;
               }
               if (!vis[next.status])
               {
            	   vis[next.status] = true;
            	   list.add(next);
               }
            }
        }
	}

	// 对象的拷贝
	private static Node getNode(Node start)
	{
       Node node = new Node();
       node.s = new StringBuffer(start.s.toString());
       node.index = start.index;
       node.step = start.step;
       node.status = start.status;
       return node;
	}

	private static int getHash(String start, int len)
	{
		int sum = 0;
		for (int i = 0; i < len; i++)
		{
           int count = 0;
           for (int j = i + 1; j < len; j++)
             if (start.charAt(i) > start.charAt(j)) count++;
           sum += count * fac[len-i-1];
		}
		return sum+1;
	}    
} 
class Node
{
	StringBuffer s;  // 记录
	int index;       // 空格
	int step;        // 步数
	int status;      // Hash地址
	
}