数据范围16个位置,考虑使用位运算来枚举每一位的点击情况,暴力check直接就可以AC。这里我们把数组设为0起点这样可以方便很多,输出的时候注意加一即可。check函数中遇到点击一个点时,整行会被切换一次,整列又被切换一次,但是交叉点只要切换一次,于是使用tmp数组用来抵消多出影响。以上就是所有的要点,很容易就可以AC了。
#include <bits/stdc++.h>
using namespace std;
int a[4][4];
int row[4], col[4], tmp[4][4];
bool check(int x) {
for (int i = 0; i < 4; ++i) {
for (int j = 0; j < 4; ++j) {
tmp[i][j] = 0;
row[i] = col[j] = 0;
}
}
for (int i = 0; i < 4; ++i) {
for (int j = 0; j < 4; ++j) {
if ((x >> (i * 4 + j)) & 1) {
++row[i];
++col[j];
--tmp[i][j];
}
}
}
for (int i = 0; i < 4; ++i) {
for (int j = 0; j < 4; ++j) {
if (a[i][j] ^ (row[i] + col[j] + tmp[i][j]) % 2) {
return false;
}
}
}
return true;
}
int cnt(int x) {
int res = 0;
for (int i = 0; i < 16; ++i) {
if ((x >> i) & 1) {
++res;
}
}
return res;
}
int main(void) {
for (int i = 0; i < 4; ++i) {
string tmp;
cin >> tmp;
for (int j = 0; j < 4; ++j) {
a[i][j] = (tmp[j] == '-' ? 0 : 1);
}
}
int res, mini = INT_MAX;
for (int i = 0; i < (1 << 16); ++i) {
if (check(i) && cnt(i) < mini) {
mini = cnt(i);
res = i;
}
}
printf("%d\n", mini);
for (int i = 0; i < 4; ++i) {
for (int j = 0; j < 4; ++j) {
if ((res >> (i * 4 + j)) & 1) {
printf("%d %d\n", i + 1, j + 1);
}
}
}
return 0;
}