思路: 枚举第一行,第二行把第一行白色的变黑,三、四如法案炮制。

C++ AC代码:

#include <cstdio>
#include <algorithm>
using namespace std;
const int n = 4, m = 4;
// 两个棋盘
int a[n + 1], b[n + 1];
int change[n + 1]; // 二进制表示那里翻了哪里没翻 1: 翻了, 0: 没翻
// x的二进制中有多少个1
int cnt1(int x) {
	int cnt = 0;
	while (x) {
		if (x & 1)
			++cnt;
		x >>= 1;
	}
	return cnt;
}
// 将白棋翻黑=>把1翻成0
int solve(int a[]) {
	int ans = INT_MAX;
	int cur[n + 1];										   // 当前正在修改的棋盘
	int cnt = 0;										   // 翻转的次数
	for (change[0] = 0; change[0] < 1 << m; ++change[0]) { // 0b0000->0b1111
		cnt = cnt1(change[0]);
		// a[0] ^ change[0] : 翻转当前棋子
		// a[0] ^ (change[0] >> 1) : 翻转当前棋子右边
		// a[0] ^ ((change[0] << 1) & ((1 << m) - 1)) : 翻转当前棋子左边, 用相同位数去翻转
		cur[0] = a[0] ^ change[0] ^ (change[0] >> 1) ^ ((change[0] << 1) & ((1 << m) - 1));
		cur[1] = a[1] ^ change[0]; //翻转下一行的中间
		for (int i = 1; i < n; ++i) {
			change[i] = cur[i - 1];																  // 翻转前一行亮着的棋子的下面那个, 把上一行按灭
			cnt += cnt1(change[i]);																  // 翻转了几次
			cur[i] = cur[i] ^ change[i] ^ (change[i] >> 1) ^ ((change[i] << 1) & ((1 << m) - 1)); // 用修改过的当前行去翻转
			cur[i + 1] = a[i + 1] ^ change[i];
		}
		if (cur[n - 1] == 0)	 // 最后一行全为0(前面的必然为0)
			ans = min(ans, cnt); // 更新答案
	}
	return ans;
}
int main() {
	// 读取
	char c;
	for (int i = 0; i < 4; ++i) 
		for (int j = 0; j < 4; ++j) {
			scanf(" %c", &c);
			if (c == 'b')
				a[i] |= 1 << j;
			else
				b[i] |= 1 << j;
	}
	// 求解
	int ans = min(solve(a), solve(b));
	if (ans > n * m)
		printf("Impossible\n");
	else
		printf("%d\n", ans);
	return 0;
}