eightbfs.java

九宫问题（八数码）的一个小软件

/*
 * EightBFS.java
 *
 * Created on February 7, 2006, 1:04 PM
 *
 * To change this template, choose Tools | Template Manager
 * and open the template in the editor.
 */

package org.ray.ninegrid;

import java.util.Vector;

/**
 *
 * @author Ray#
 */
public class EightBFS extends AbstractEightAnalyse {    
    private Vector<Status> queue;
    
    private EightBFS(){
        super();
        hash.put(new Status(end,0),new Operation('0'));        
        queue=new Vector<Status>();
    }
    
    private static final EightBFS instance=new EightBFS();
    
    public static EightBFS getInstance(int[] st){
        instance.start=st;
        return instance;
    }
    
    public String search() {
        time=System.currentTimeMillis();
        Runtime.getRuntime().gc();
        mem=Runtime.getRuntime().freeMemory();
        Status a=new Status(start,0);
        if(!hash.containsKey(a)){
            if(queue.size()==0){
                queue.add(new Status(end,0));
            }
            Status cur;
            do{
                cur=queue.remove(0);
                expand(cur.value,cur.level);
            }while(!cur.equals(new Status(start,0)));
        }
        mem=Math.abs(mem-Runtime.getRuntime().freeMemory());
        oplist=result();
        time=System.currentTimeMillis()-time;
        return oplist;
    }
    
    @Override
    protected void valid(int[] nextStatus, int nextLevel, char operation) {
        Status temp=new Status(nextStatus,nextLevel);
        if(!hash.containsKey(temp)){
            hash.put(temp,new Operation(operation));
            queue.add(temp);
        }
    }
    
    @Override
    protected String result() {
        StringBuffer sb=new StringBuffer();
        Status st=new Status(start,0);
        Status ends=new Status(end,0);
        char op='1';
        while(!st.equals(ends)){
            op=opposite(hash.get(st).op);
            sb.append(op);
            st=new Status(move(st.value,op),0);
        }
        return sb.toString();
    }
    
    public int[] getStart() {
        return start;
    }
    
    private void setStart(int[] start) {
        this.start = start;
    }
    
    @Override
    public void clear(){
        hash.clear();
        queue.clear();
    }
}