Untitled

Turn Over Game

#include<iostream>
using namespace std;
#define MAX_SIZE 4
#define SINH_MAX 65536 // 2^16

int map[MAX_SIZE][MAX_SIZE];
int mapCopy[MAX_SIZE][MAX_SIZE];
int arrSinh[SINH_MAX][16];
int arr[16];

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

/* Turn over at x,y */
void turnOver(int x, int y){
	mapCopy[x][y] = 1 - mapCopy[x][y];
	for (int i = 0; i < 4; i++){
		int x1 = x + dx[i];
		int y1 = y + dy[i];
		if (x1>=0 && x1<4 && y1>=0 && y1<4){
			mapCopy[x1][y1] = 1 - mapCopy[x1][y1];
		}
	}
}

bool checkMapCopy(){
	for (int i = 0; i < 4; i++){
		for(int j=0; j < 4; j++){
			if (mapCopy[i][j] != mapCopy[0][0]) return false;
		}
	}
	return true;
}

int hang = 0;
void sinh(int k){
	if (k == 16){
		for (int i = 0; i < 16; i++) {
			arrSinh[hang][i] = arr[i];
        }
		hang++;
		return;
	}
	arr[k] = 0; sinh(k+1);
	arr[k] = 1; sinh(k+1);
}

void resetMap(){
	// reset map copy
	for (int i = 0; i < 4; i++){
		for (int j = 0; j < 4; j++){
			mapCopy[i][j] = map[i][j];
		}
	}
}

/* main */
int main(){
	freopen("input.txt","r",stdin);
	int TC; cin >> TC;
	int ans;
	for (int tc = 1; tc <= TC; tc++){
		/* Input */ 
		for (int i = 0; i < 4; i++){
			for (int j = 0; j < 4; j++){
				char x; cin >> x;
				map[i][j] = (x=='w')?0:1;
			}
		}
		
		/* Program */ 
		// Sinh nhi phan chuoi 16
		sinh(0);
		ans = 1000000;
		for (int i = 0; i < SINH_MAX; i++){
			resetMap();
			int sum = 0;
			// lat theo tung truong hop i
			for (int j = 0; j < 16; j++){
				if(arrSinh[i][j] == 1){
					// lat 
					sum++;
					turnOver(j/4,j%4);
				}
			}
			// check map full
			if (checkMapCopy()){
				if (ans > sum) ans = sum;
			} 
		}

		/* Output */
		cout << "Case #" << tc << endl;
		if (ans < 1000000) cout << ans << endl;
		else cout << "impossible" << endl;

	}
	return 0;
}