flipgame1.java

来自「PKU中一些数据结构基本算法题的java实现」· Java 代码 · 共 220 行

package PKU;
import java.util.*;


public class FlipGame1 {

	static int[] dx = {0,-1,0,1,0};
	static int[] dy={0,0,-1,0,1};
	static Queue<byte[][]> q = new ListQueue();
	static Map<String,Integer> result = new HashMap<String,Integer>();
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		byte g[][] = new byte[4][4];
		byte v1[][] = new byte[4][4];
		byte v2[][] = new byte[4][4];
		for(int i=0;i<4;i++){
			for(int j=0;j<4;j++){
				v1[i][j]=0;
			}
		}
		for(int i=0;i<4;i++){
			for(int j=0;j<4;j++){
				v2[i][j]=1;
			}
		}
		
		Scanner cin = new Scanner(System.in);
		for(int i=0;i<4;i++){
			String str = cin.next();
			for(int j=0;j<4;j++){
				char c = str.charAt(j);
				if(c=='b')g[i][j]=1;
				else g[i][j]=0;
			}
		}
		long time = System.currentTimeMillis();
		int step = BFS(v1,v2,0,g);
		System.out.println(System.currentTimeMillis()-time);
		System.out.println(step==-1?"Impossible":step);

	}

	static int BFS(byte[][] v1,byte[][] v2, int step, byte[][] question){
		record(v1,step);
		q.offer(v1);
		record(v2,step);
		q.offer(v2);
		while(!q.isEmpty()){
			byte[][] w = q.poll();
			step = getResult(w);
			
			if(check(question,w)) 
				return step;
			/*
			if(q.size()==65500){
				int i =1;
				i++;
			}*/
			for(int i=0;i<4;i++){
				for(int j=0;j<4;j++){
					byte[][] x = change(w,i,j);
					Integer integer = getResult(x);
					if (integer == null) {
						record(x, step + 1);
						q.offer(x);
					}		
				}
			}
		}
		return -1;
		
	}
	static boolean check(byte[][] g1,byte[][] g2){
		for(int i=0;i<4;i++){
			for(int j=0;j<4;j++){
				if(g1[i][j]!=g2[i][j]) return false;
			}
		}
		return true;
	}
	static Integer getResult(byte[][] g){
		String str = translate(g);
		return result.get(str);
	}
	
	static byte[][] change(byte[][]h, int x,int y){
		byte[][] g = new byte[4][4];
		for(int i=0;i<4;i++){
			for(int j=0;j<4;j++){
				g[i][j]=h[i][j];
			}
		}
		for(int i=0;i<5;i++){
			int curx=x+dx[i];
			int cury=y+dy[i];
			if(curx<0||cury<0||curx>3||cury>3) continue;
			if(g[curx][cury]==1){
				g[curx][cury]=0;
			}
			else g[curx][cury]=1;
		}
		return g;
	}
	
	
	static String translate(byte[][] g){
		int k=0;
		StringBuffer str = new StringBuffer();
		for(int i=0;i<4;i++){
			for(int j=0;j<4;j++){
				str.append(g[i][j]);
				k++;				
			}
		}
		return str.toString();
	}
	static void record(byte[][] g,int r){
		String key = translate(g);
		result.put(key, r);
	}

}


class ListQueue implements Queue{

	private List l = new LinkedList();
	public Object element() {
		// TODO Auto-generated method stub
		return null;
	}

	public boolean offer(Object o) {
		return l.add(o);
	}

	public Object peek() {
		// TODO Auto-generated method stub
		return null;
	}

	public Object poll() {
		// TODO Auto-generated method stub
		return l.remove(0);
	}

	public Object remove() {
		// TODO Auto-generated method stub
		return null;
	}

	public boolean add(Object o) {
		// TODO Auto-generated method stub
		return false;
	}

	public boolean addAll(Collection c) {
		// TODO Auto-generated method stub
		return false;
	}

	public void clear() {
		// TODO Auto-generated method stub
		
	}

	public boolean contains(Object o) {
		// TODO Auto-generated method stub
		return false;
	}

	public boolean containsAll(Collection c) {
		// TODO Auto-generated method stub
		return false;
	}

	public boolean isEmpty() {
		// TODO Auto-generated method stub
		return l.isEmpty();
	}

	public Iterator iterator() {
		// TODO Auto-generated method stub
		return null;
	}

	public boolean remove(Object o) {
		// TODO Auto-generated method stub
		return false;
	}

	public boolean removeAll(Collection c) {
		// TODO Auto-generated method stub
		return false;
	}

	public boolean retainAll(Collection c) {
		// TODO Auto-generated method stub
		return false;
	}

	public int size() {
		// TODO Auto-generated method stub
		return 0;
	}

	public Object[] toArray() {
		// TODO Auto-generated method stub
		return null;
	}

	public Object[] toArray(Object[] a) {
		// TODO Auto-generated method stub
		return null;
	}
	
}