> 证明:要使一个为'+'的符号变为'-',必须其相应的行和列的操作数为奇数;可以证明,如果'+'位置对应的行和列上每一个位置都进行一次操作,则整个图只有这一'+'位置的符号改变,其余都不会改变.
> 设置一个4*4的整型数组,初值为零,用于记录每个点的操作数,那么在每个'+'上的行和列的的位置都加1,得到结果模2(因为一个点进行偶数次操作的效果和没进行操作一样,这就是楼上说的取反的原理),然后计算整型数组中一的
> 个数即为操作数,一的位置为要操作的位置(其他原来操作数为偶数的因为操作并不发生效果,因此不进行操作)

举个例子给像我这样第一次做这种题目的朋友
例如 一个二维数组 a[4][4]，也就是说 a[0][0]='+'的时候，我们讲 i=0，j=0的所有元素给它来操作一次，总共就是七个元素会起作用是吧 ，就是：a[0][0],a[0][1],a[0][2],a[0][3],a[1][0],a[2][0],a[3][0] 那么 a[0][0]受其他六个元素所作用和自身一次作用，也就是七次，奇数次作用等于作用一次，结果a[0][0] 就是‘-’了，而其他每个元素，受各自每一行的元素作用，也就是四次，偶数次是等于没起作用了。那么最后的结果就是达到了 a[0][0]的改变，其余就不会变。这次像我这样比较蠢的人一开始还怀疑说 i!=0,j！=0的其他元素不会受到影响吗？ 不会的，你把数组给画出来，除a[0][0]之外，满足i=0，j=0的元素给他们划六条横线就可以看出来，其他元素是被作用了两次，也就是等于没作用到！ ：）

• Re:关于楼上理论我的证明: (16) wsy217 2009-04-15 16:36:27
  • 试证其为最小步数 (849) temporary1 2009-08-16 15:56:40