POJ 2965.The Pilots Brothers’ refrigerator
Ideas题意：给你4*4的矩阵。每个点有两种状态，+代表关，-代表开。每个点有一个操作就是该点所在行列所有状态翻转。问最少多少次可以打开全部开关，并且输出最少个数情况下翻转的点。
先梳理一下题目给的测试样例的操作步骤：
首先需要知道一点：一个开关翻转偶数次状态不变，翻转奇数次状态改变。（奇变偶不变）
然后再深入一步：要使一个为+的符号变为-，必须其相应的行和列的操作数为奇数。
如果+位置对应的行和列上每一个位置都进行一次操作，则整个图只有这个+位置的符号改变，其余都不会改变。
假如只有(1, 1)位置上为+，那么第一行和第一列全部翻转一遍之后，只有(1, 1)位置上变为-，其它位置没有改变。
设置一个4*4的整型数组mark，初值为零，用于记录每个位置的操作次数。
那么在每个+上的行和列的的位置都加1，也就是说这个+对应位置的行和列都翻转一遍，结果只有这个+位置变为-，其它不变。
最后，有些位置翻转了偶数次，没有改变，有些位置翻转了奇数次，这些位置就是要进行翻转的位置。
因此mark可以简化为bool类型的数组，为0或false表示翻转偶数次，为1或true表示翻转奇数次。
Code C++#include #include using namespace std; bool mark[4][4]; int main() { memset(mark, 0, sizeof(mark)); for(int i = 0; i < 4; i++) { for(int j = 0; j < 4; j++) { char ch; cin >> ch; if(ch == '+') { mark[i][j] = !mark[i][j]; for(int k = 0; k < 4; k++) { mark[i][k] = !mark[i][k]; mark[k][j] = !mark[k][j]; } } } } int step = 0; int p_i[16], p_j[16]; for(int i = 0; i < 4; i++) { for(int j = 0; j < 4; j++) { if(mark[i][j]) { p_i[step] = i + 1; p_j[step] = j + 1; step++; } } } cout << step << endl; for(int i = 0; i < step; i++) { cout << p_i[i] << " " << p_j[i] << endl; } return 0; }
