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

testttttttttt case
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

ket qua
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;

}