思路: 枚举第一行,第二行把第一行白色的变黑,三、四如法案炮制。
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;
}