POJ 2965 The Pilots Brothers' refrigerator 贪心神解【转】

//POJ 2965 The Pilots Brothers' refrigerator// http://www.cppblog.com/Yusi-Xiao/archive/2010/07/05/77385.html
// 先看一个简单的问题,如何把'+'变成'-'而不改变其他位置上的状态?
// 答案是将该位置(i,j)及位置所在的行(i)和列(j)上所有的handle更新一次。
// 结果该位置被更新了7次,相应行(i)和列(j)的handle被更新了4次,剩下的被更新了2次.
// 被更新偶数次的handle不会造成最终状态的改变.
// 因此得出高效解法,在每次输入碰到'+'的时候, 计算所在行和列的需要改变的次数
// 当输入结束后,遍历数组,所有为奇数的位置则是操作的位置,而奇数位置的个数之和则是最终的操作次数.
// 但这种算法只对n为偶数时适用
// PS:该题不会有"Impossible"的情况.

#include<iostream>
#include<memory.h>
using namespace std;
#define INF 0x7fffffff
int p[5][5];
int main(void)
{
char c;
memset(p, 0, sizeof(p));
for (int i = 1; i <= 4; i++)
for (int j = 1; j <= 4; j++)
{
cin >> c;
if (c == '+')
{
for (int k = 1; k <= 4; k++)
{
p[i][k]++;
p[k][j]++;
}
p[i][j]--;
}
}
int sum = 0;
for (int i = 1; i <= 4; i++)
for (int j = 1; j <= 4; j++)
sum += p[i][j]%2;
cout << sum << endl;
for (int i = 1; i <= 4; i++)
for (int j = 1; j <= 4; j++)
if
(p[i][j]%2)
cout << i << " " << j << endl;
//
system("pause");
return 0;
}