Untitled

 avatar
unknown
plain_text
2 years ago
1.5 kB
4
Indexable
#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;
}
Editor is loading...