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

#include<iostream>
using namespace std;

char a[4][4];
int b[4][4];
int ans;
int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };

bool checkColor() {
	int sum = 0;
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			sum += b[i][j];
		}
	}
	if (sum == 16 || sum == 0) return true;
	return false;
}

void changeColor(int x, int y) {
	b[x][y] = 1 - b[x][y];
	for (int i = 0; i < 4; i++) {
		int xx = x + dx[i];
		int yy = y + dy[i];
		if (xx >= 0 && xx < 4 && yy >= 0 && yy < 4) {
			b[xx][yy] = 1 - b[xx][yy];
		}
	}
}

void backTrack(int x, int y, int count) {
	if(checkColor()){
		if (count < ans) {
			ans=count;
		}
		return;
	}
	if(x>=4) return;
	if(count > ans) return;
	if(y+1<4){
		changeColor(x,y);
		backTrack(x,y+1, count+1);
		changeColor(x,y);
		backTrack(x,y+1, count);
	}
	else{
		changeColor(x,y);
		backTrack(x+1,0, count+1);
		changeColor(x,y);
		backTrack(x+1,0, count);
	}
}


int main(){
	int test;
	cin >> test;
	for(int tc=1; tc <=test; tc++){
		for(int i =0; i<4; i++){
			for(int j=0; j<4; j++){
				cin >> a[i][j];
			}
		}
		
		for(int i =0; i<4; i++){
			for(int j=0; j<4; j++){
				if(a[i][j] == 'b') b[i][j] =1;
				else if(a[i][j] == 'w') b[i][j] =0;
			}
		}
		ans = 100000000;
		backTrack(0,0,0);
		cout <<"Case #" << tc <<endl;
		if(ans == 100000000) cout << "impossible" << endl;
		else cout << ans <<endl;
	}
	return 0;
}