Untitled

 avatar
user_1164828
plain_text
a month ago
1.3 kB
0
Indexable
Never
///Turn over game

#include<iostream>
using namespace std;

char map[10][10];
int cnt;
int ans;
int n = 4;
int dx[] = {1,0,0,-1};
int dy[] = {0,1,-1,0};

bool check(){
	int w = 0, b =0;
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			if(map[i][j] =='w') w++;
			else b++;
		}
	}
	return w == n*n || b == n*n;
}

void changeColor(int r, int c){
	if(map[r][c] == 'w'){
		map[r][c] = 'b';
	}
	else map[r][c] = 'w';
	int xN, yN;
	for(int i=0; i<4; i++){
		xN = r + dx[i];
		yN = c + dy[i];
		if(xN >= 0 && xN <= n-1 && yN >=0 && yN <=n-1){
			if(map[xN][yN] == 'w'){
				map[xN][yN] = 'b';
			}
			else{
				map[xN][yN] = 'w';
			}
		}
	}
}

int min(int x, int y){
	return (x<y) ? x : y;
}

void BT(int k, int cnt){
	if (check()){
		ans = min(ans, cnt);
	}
	if(cnt >= ans) return;
	if(k==16) return;
	for(int i=0; i<2; i++){
		if (i==1){
			changeColor(k/n,k%n);
			BT(k+1,cnt+1);
			changeColor(k/n,k%n);
		}
		else{
			BT(k+1,cnt);
		}
	}
}

int main(){
	//freopen("Text.txt", "r", stdin);
	int T;
	cin >> T;
	for(int tc = 1; tc<=T; tc++){
		
		for(int i=0; i<n; i++){
			cin >> map[i];
		}
		cnt = 0;
		ans = 1000000;
		BT(0,0);

		cout << "Case #" << tc << endl;
		if(ans == 1000000){
			cout << "impossible" << endl;
		}
		else cout<< ans << endl;
	}
	return 0;
}
Leave a Comment