今晚上做了2965，做法和1753差不多，毕竟在POJ训练计划上都是属于一样的题目，枚举
代码就不重复了，和1753差不了多少。后来我在网上搜了这道题目，竟然发现有个大神竟然出来了一个很简单的算法。
真是厉害，看样子找规律很重要啊！！！！
作者网址：http://www.cppblog.com/Yusi-Xiao/archive/2010/07/05/77385.html
他的思路是：
先看一个简单的问题,如何把'+'变成'-'而不改变其他位置上的状态?
答案是将该位置(i,j)及位置所在的行(i)和列(j)上所有的handle更新一次。
结果该位置被更新了7次,相应行(i)和列(j)的handle被更新了4次,剩下的被更新了2次.
被更新偶数次的handle不会造成最终状态的改变.
因此得出高效解法,在每次输入碰到'+'的时候, 计算所在行和列的需要改变的次数
当输入结束后,遍历数组,所有为奇数的位置则是操作的位置,而奇数位置的个数之和则是最终的操作次数.
再看他的代码
:
#include <stdio.h>
#define Len 4
void main()
{
int handles[Len][Len] = {0};
int i, j, k, step = 0;
char c;
// 核心算法，统计翻转的总次数
for (i = 0; i < Len; ++i)
{
for (j = 0; j < Len; ++j)
{
scanf("%c", &c);
if ('+' == c)
{
handles[i][j]++;
for (k = 0; k < Len; ++k)
{
handles[i][k]++; // 这种算法重复计算i,j 处，但是对于只需要判断奇偶来说无所谓
handles[k][j]++;
}
}
}
getchar();//一开始的代码这位大神竟然没有接受\n，也不知道因为什么！
}
// 统计奇数的个数
for (i = 0; i < Len; ++i)
{
for (j = 0; j < Len; ++j)
{
if (handles[i][j] % 2)
{
step++;
}
}
}
printf("%d\n", step);
// 打印奇数的位置
for (i = 0; i < Len; ++i)
{
for (j = 0; j < Len; ++j)
{
if (handles[i][j] % 2)
{
printf("%d %d\n", i + 1, j + 1);
}
}
}
}