import java.util.*;

public class BestMisMatch extends DFS
{

    private int depth=0;
    public int getDepth() { return depth; }
    public void setDepth(int d) { depth=d; }
    
    private int thescore;

    public int score()
    {
	return depth+thescore;
    }

    public BestMisMatch(int ii)
    {
	super(ii);
    }

    public BestMisMatch(DFS t, DFS tee)
    {
	puzzle=t.getPuzzle();
	thescore=doScore(tee);
    }

    private int doScore(DFS other)
    {
	int[][] p = other.getPuzzle();
	int score = 0;
	for (int i=0; i<p.length; i++)
	    for (int j=0; j<p[i].length; j++)
		if (p[i][j]!=puzzle[i][j])
		    score++;
	return score;
    }
	
    private class CC implements Comparator<BestMisMatch>
    {
	public int compare(BestMisMatch a, BestMisMatch b)
	{
	    if (a.score() < b.score())
		return -1;
	    if (a.score() > b.score())
		return 1;
	    return 0;
	}
	public boolean equals(Object o)
	{
	    if (!(o instanceof BestMisMatch))
		return false;
	    return true;
	}
    }

    public static boolean inList(Object o, PriorityQueue v)
    {
	for (Object oo: v)
	    {
		//System.out.print(((BestMisMatch)oo).score());
		if (((DFS)o).isSame((DFS)oo))
		    {
			//System.out.println();
			return true;
		    }
	    }
	//System.out.println();
	return false;
    }


    public static void main(String[] s)
    {
	new BestMisMatch(s);
    }

    public BestMisMatch(String[] s)
    {
	DFS tee = new DFS(Integer.parseInt(s[2]));
	tee.readFile(s[0]);
	DFS ee = new BestMisMatch(Integer.parseInt(s[2]));
	ee.readFile(s[1]);
	BestMisMatch bmm=new BestMisMatch(ee, tee);
	PriorityQueue openList=new PriorityQueue(100, new CC());
	openList.add(bmm);
	Vector closedList=new Vector();

	HashMap closedMap = new HashMap();
	HashMap openMap = new HashMap();

	System.out.println(tee);
	System.out.println(ee.toString());

	int ld=0;
	for (long i=0; i<10000000; i++)
	    {

		Vector legalM = ee.legalMoves();
		for (Object o : legalM)
		    {
			BestMisMatch b=new BestMisMatch((DFS)o, tee);
			if (b.score()==0)
			    {
				System.out.println("GOTIT" + i + "Number of moves: " + (((BestMisMatch)ee).getDepth()+1));
				System.exit(1);
			    }
			b.setDepth(((BestMisMatch)ee).getDepth()+1);
			if (!openMap.containsKey(b.toString()))
			    {
				openList.add(b);
				openMap.put(b.toString(), null);
			    }
		    }
		if (i % 1000 == 1)
		    System.out.println(i + "  " + openList.size() + "  " + (openList.size()/(i*1.0)));
		ee = (DFS) openList.remove();
		//System.out.println(((BestMisMatch)ee).score());
		//closedList.add(ee);
		//closedMap.put(ee.toString(), null);
		//System.out.println(ee.toString() + "\n");
	    }
	
    }


}