Untitled

/*Turn Over Game
As in , there is a 4×4 sized table. In a grid of the table, there are white or black stones. When you choose a position of stone randomly, the stone and four stones adjacent to the up, down, left and right sides of the stone will turn to the opposite color like turning a white stone to a black & a black stone to a white. Let’s suppose this process as a calculation.


Using such a calculation, you want to change all the stones on the table into all whites or all blacks. Find out the minimum operation count at this time.

Time limit: 1 second (java: 2 seconds)

[Input]
Several test cases can be included in the inputs. T, the number of cases is given in the first row of the inputs. After that, the test cases as many as T (T ≤ 30) are given in a row.
Table info is given without blank over four rows per each test case. Colors are indicated like white for ‘w’ and black for ‘b’.

[Output]
Output the minimum operation count to change all colors as white or black on the first row per each test case. If not possible, output "impossible" .

[I/O Example]
Input
2
bwwb
bbwb
bwwb
bwww
bwbw
wwww
bbwb
bwwb

Output
Case #1 

4 

Case #2
impossible*/

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.PrintStream;
import java.util.Scanner;

public class TurnOverGame {
	static{
		try {
			System.setIn(new FileInputStream("src/inp.txt"));
//			System.setOut(new PrintStream("src/out.txt"));
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
	static Scanner scanner=new Scanner(System.in);
	static int res,dir[][]={{-1,0},{1,0},{0,1},{0,-1}};
	
	static class Node{
		int opt,cost;
		Node link;
		Node(int opt,int cost){this.opt=opt;this.cost=cost;}
	}
	
	static class Queue{
		Node front,rear;
		int n;
		void push(Node node){
			++n;
			if(front==null){
				front=rear=node;
				return;
			}
			rear.link=node;
			rear=node;
		}
		void pop(){
			if(front==null)
				return;
			--n;
			front=front.link;
			if(front==null)
				rear=null;
		}
	}
	
	/*sol: bt tu 1 o trang/den
	 * neu o ke tiep khac mau cua no thi di den no va chua duyet
	 * 
	 * */
	
	static int flip(int num,int j){
		int xor=1<<(j-1);	//dich j bit
		
		if(j==1||j==5||j==9||j==13)
			xor|=1<<(j);
		else if(j==4||j==8||j==12||j==16)
			xor|=1<<(j-2);
		else{
			if(j<16)
				xor|=1<<(j);
			if(j-2>0)
				xor|=1<<(j-2);
			else
				xor|=1;
		}
		
		if(j+3<16)
			xor|=1<<(j+3);
		if(j-5>=0)
			xor|=1<<(j-5);
		
		return xor;
	}
	
	static String toBinStr(int a){
		StringBuilder builder=new StringBuilder();
		if(a==0){
			builder.append(0);
			return builder.toString();
		}
		while(a>0){
			builder.append(a%2);
			a>>=1;
		}
		return builder.reverse().toString();
	}
	
	static int nextNumber(char[] string,int x,int y){
		int[][] string2=new int[4][4];
		int idx=0;
		for(int i=0;i<4;++i) for(int j=0;j<4;++j) string2[i][j]=string[idx++]=='0'?0:1;
		string2[x][y]=string2[x][y]==0?1:0;
		for(int i=0;i<4;++i){
			int nx=x+dir[i][0],ny=y+dir[i][1];
			if(nx>=0 && nx<4 && ny>=0 && ny<4)
				string2[nx][ny]=string2[nx][ny]==0?1:0;
		}
		StringBuilder builder=new StringBuilder();
		for(int i=0;i<4;++i)
			for(int j=0;j<4;++j)
				builder.append(string2[i][j]);
		return Integer.parseInt(builder.toString(),2);
	}
	
	static void exec(int test){
		StringBuilder builder=new StringBuilder();
		
		for(int i=0;i<4;++i) {
			char[] tmp=scanner.next().toCharArray();
			for(int j=0;j<4;++j) 
				if(tmp[j]=='b') builder.append(1);
				else builder.append(0);
		}

		int first=Integer.parseInt(builder.toString(),2);
		
		Queue queue=new Queue();
		boolean[] vis=new boolean[65536];
		vis[first]=true;
		queue.push(new Node(first,0));
		
		while(queue.n>0){
			int opt=queue.front.opt;
			int cost=queue.front.cost;
			queue.pop();
			
			if((opt&65535)==65535 || opt==0){
				System.out.printf("Case #%d\n%d\n",test,cost);
				return;
			}
			
//			char[] curr=toBinStr(opt).toCharArray();
//			for(int i=0;i<4;++i)
//				for(int j=0;j<4;++j){
//					int next=nextNumber(curr,i,j);
//					if(!vis[next]){
//						if((next&65535)==65535 || next==0){
//							System.out.printf("Case #%d\n%d\n",test,cost+1);
//							return;
//						}
//						vis[next]=true;
//						queue.push(new Node(next,cost+1));
//					}
//				}
			for(int i=1;i<=16;++i){
				int flipopt=flip(opt,i);
				int next=opt^flipopt;
				if(!vis[next]){
					if((next&65535)==65535 || next==0){
						System.out.printf("Case #%d\n%d\n",test,cost+1);
						return;
					}
					vis[next]=true;
					queue.push(new Node(next,cost+1));
				}
			}
		}
		
		System.out.printf("Case #%d\nimpossible\n",test);
	}
	
	public static void main(String[] args) {
		int t=Integer.parseInt(scanner.next());
		
		for(int test=1;test<=t;++test)
			exec(test);
		
		scanner.close();
	}
}