flipgame.java

PKU中一些数据结构基本算法题的java实现

package PKU.DFS;

import java.util.*;


/**
 * ID：1753
 * DFS,值得注意的是一个子什么时候被翻开对结果没有影响，因此可以按顺序翻开棋子。dd就是用于顺序转化为相应子的坐标
 * 
 * @author yhm
 *
 */
public class FlipGame {

	static int[] dx = {0,-1,0,1,0};
	static int[] dy={0,0,-1,0,1};

	static int step;
	static int min;
	static int[][] g = new int[6][6];


	


	/**
	 * @param args
	 */
	public static void main(String[] args) {
		
		Scanner cin = new Scanner(System.in);
		for(int i=1;i<=4;i++){
			String str = cin.next();
			for(int j=1;j<=4;j++){
				char c = str.charAt(j-1);
				if(c=='b')g[i][j]=1;
				else g[i][j]=0;
			}
		}
		min=17;
		step=0;
		dfs(1);
		System.out.println(min==17?"Impossible":min);


	}
	static boolean check(){
		for(int i=1;i<=4;i++){
			for(int j=1;j<=4;j++){
				if(g[i][j]!=g[1][1])return false;
			}
		}
		return true;
	}
	static void change(int x,int y){
		for(int i=0;i<5;i++){
			int curx=x+dx[i];
			int cury=y+dy[i];
			g[curx][cury]=(g[curx][cury]+1)%2;
		}
	}



	
	static void dfs(int k){
		if(check()){
			if(step<min)min=step;
		}
		else if(k>16){
			return;
		}
		else{
			int x = 0;
			int y = 0;
			if(k%4==0){
				y = 4;
				x = k/4;
			}
			else{
				y = k%4;
				x = k/4+1;
			}

			change(x,y);
			step++;
			dfs(k+1);
			change(x,y);
			step--;
			dfs(k+1);
		}

		
	}

}