这道题和算法进阶指南的一道题解法一样,必须另操作为奇数。见证明过程
证明:要使一个为'+'的符号变为'-',必须其相应的行和列的操作数为奇数;可以证明,如果'+'位置对应的行和列上每一个位置都进行一次操作,则整个图只有这一'+'位置的符号改变,其余都不会改变.
设置一个4*4的整型数组,初值为零,用于记录每个点的操作数,那么在每个'+'上的行和列的的位置都加1,得到结果模2(因为一个点进行偶数次操作的效果和没进行操作一样,这就是楼上说的取反的原理),然后计算整型数组中一的
个数即为操作数,一的位置为要操作的位置(其他原来操作数为偶数的因为操作并不发生效果,因此不进行操作)
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int main() {
char s[5][5];
int mark[5][5];
int x[20], y[20];
memset(mark, 0, sizeof(mark));
for (int i = 0; i < 4; i++) cin >> s[i];
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
if (s[i][j] == '+') {
mark[i][j] = !mark[i][j];//下面的操作中,i,j这个位置翻转了操作了两次,等于没操作,所以上边这里再操作一次,这样让这个位置 也被操作了
for (int k = 0; k < 4; k++) {
mark[i][k] = !mark[i][k];
mark[k][j] = !mark[k][j];
}
}
}
}
int ans = 0;
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
if (mark[i][j]) {
x[ans] = i + 1;
y[ans] = j + 1;
ans++;
}
}
}
printf("%d\n", ans);
for (int i = 0; i < ans; i++) printf("%d %d\n", x[i], y[i]);
return 0;
}