Untitled

Turn Over Game

*******************************
Input
2
bwwb
bbwb
bwwb
bwww
bwbw
wwww
bbwb
bwwb
Output
Case #1 
4 
Case #2
impossible
*******************************
50
wbwb
wbbw
wbww
wbww
bbwb
bbbw
wbww
bwwb
bbbb
wwbw
bwbb
bbbb
bwwb
bwww
wwbb
wbbb
wbbb
bbww
bbwb
wwbw
wbwb
bwww
bwbw
wwbw
wbww
wbww
bbbw
bwwb
wbbw
wbwb
bbbb
wbww
wbww
wbwb
wwww
bwwb
bwwb
bbww
bwww
bbbw
bwbw
wwbw
wwww
wbww
bwbb
bwww
bwbb
wwww
wbbw
bbbb
bwww
bbww
wbwb
bwbw
bwbw
bwbw
bbww
bbwb
bbbw
wwwb
bwbb
wbbw
wwww
bwbb
bbww
wbbw
bbbw
wbbw
bwbb
bbww
wbww
wbbb
bwwb
bbww
wwww
wwbw
bbbb
bwbb
wwww
bwww
bwbw
wwbw
wwbb
wwww
bwww
bwbb
bbwb
wwwb
wwww
bwbw
bbbb
wbww
bwbb
wwwb
wbww
bwwb
bwww
bbwb
wwbb
bbwb
wbww
bwww
wbww
bwwb
bwbb
wbbw
bwwb
wbww
bbbw
wwww
wwbw
wbbw
wwbw
bbbw
bwwb
wbbb
bwbw
bwbb
bbwb
bwbw
bwww
wwww
bbbw
wwbw
wbww
wbww
wbbb
wbbw
bbbb
wwww
bbbb
bwwb
wwww
wbwb
wbwb
bwwb
bbwb
bbww
bbbb
bwwb
wwww
wwbb
wbbw
wbww
bbwb
wwww
wwww
wwww
wwww
wwww
bwbb
bbww
bwbb
wwww
wbbb
bwww
bwbw
wwbb
wbww
bbbb
bwww
wbwb
wwbb
wbbb
wbww
wwbb
bbbw
wbwb
wwwb
bbbw
bwww
wwwb
bwbb
bwbb
wwww
wbwb
wbbw
bwwb
bbbw
bbww
wbwb
bwbw
wwbb
wbwb
bwbb
bbbb
wbwb
bwwb
bwbw
bwwb
bwbw
bwww
bwbw
wwww
bbwb
bwwb
bbbb
bbbb
bbbb
bbbb
*******************************
Case #1
5
Case #2
3
Case #3
3
Case #4
5
Case #5
5
Case #6
5
Case #7
4
Case #8
3
Case #9
6
Case #10
4
Case #11
4
Case #12
3
Case #13
5
Case #14
5
Case #15
5
Case #16
5
Case #17
5
Case #18
5
Case #19
5
Case #20
2
Case #21
4
Case #22
6
Case #23
3
Case #24
5
Case #25
3
Case #26
5
Case #27
5
Case #28
4
Case #29
4
Case #30
5
Case #31
4
Case #32
4
Case #33
4
Case #34
3
Case #35
4
Case #36
3
Case #37
impossible
Case #38
impossible
Case #39
4
Case #40
4
Case #41
2
Case #42
5
Case #43
5
Case #44
3
Case #45
3
Case #46
5
Case #47
5
Case #48
4
Case #49
impossible
Case #50
0
*******************************
CODE:
#include<iostream>
using namespace std;

int arr[4][4];
int dx[4]= {-1,0,0,1};
int dy[4]= {0,-1,1,0};
int m=1000000;

void lat(int x, int y){
	arr[x][y]= 1- arr[x][y];
	for(int i=0;i<4;i++){
		int tempx= x+dx[i];
		int tempy= y+dy[i];
		if(tempx>=0 && tempx<4 && tempy >= 0 && tempy<4){
			arr[tempx][tempy]= 1- arr[tempx][tempy];
		}
	}
}

bool check(){
	int num= arr[0][0];
	for(int i=0;i<4;i++){
		for(int j=0;j<4;j++){
			if(arr[i][j]!=num)return false;
		}
	}
	return true;
}
void Try(int x, int y,int step){
	if(check()){
		if(step<m){
			m=step;
		}
		return;
	}
	if(x>=4)return;
	if(step>m){
		return;
	}

	if(y+1<4){
		lat(x,y);
		Try(x, y+1,step+1);
		lat(x,y);
		Try(x, y+1,step);
	}
	else{
		lat(x,y);
		Try(x+1, 0,step+1);
		lat(x,y);
		Try(x+1, 0,step);
	}

}

int main(){
	freopen("input.txt","r",stdin);
	int t;
	cin>>t;

	for(int i=1;i<=t;i++){
		char x;
		for(int h=0;h<4;h++){
			for(int k=0;k<4;k++){
				cin>>x;
				arr[h][k] = (x=='w')?0:1;
			}
		}
		m=1000000;
		Try(0,0,0);
		cout<<"Case #"<<i<<endl;
		if(m==1000000){
			cout<<"impossible"<<endl;
		}
		else 
			cout<<m<<endl;
	}
	return 0;

}