poj 2965 The Pilots Brothers' refriger

解题思路

题意：

门上有16个handle，每个handle要么开要么关， 每个handle改变状态时同一行同一列的都会改变。当全部handle状态为open时，整个门就打开了。问的是最少要改变多少个handle，才能把门打开，

 

思路：

       做完1753后做这个，就感觉差不多，不就是改变一些位嘛。确实思路差不多，把所有的handle用一个整数表示状态。然后bfs+枚举所有可能的状态。其中异或的对象为了省时间可以直接给出来。

unsigned int offset[16] = { 0xf888, 0xf444, 0xf222, 0xf111,

                         0x8f88, 0x4f44, 0x2f22, 0x1f11,

                         0x88f8, 0x44f4, 0x22f2, 0x11f1,

                         0x888f, 0x444f, 0x222f, 0x111f,};

不同的是还要输出改变了哪些handle，这个把我纠结死了，想了很久，后来算是想到个方法，每次改变时，记录下先前的状态和handle位置，最后再倒推出来，因为改变的handle的先后顺序变了结果也不会变，所以直接输出来就ok了。

       一次AC，真爽，可是时间花了不少，后来看discuss，发现里面讨论了种很高效的方法，有人如此总结：

“先看一个简单的问题,如何把'+'变成'-'而不改变其他位置上的状态?答案是将该位置(i,j)及位置所在的行(i)和列(j)上所有的handle更新一次,结果该位置被更新了7次,相应行(i)和列(j)的handle被更新了6次,剩下的被更新了4次.被更新偶数次的handle不会造成最终状态的改变.因此得出高效解法,在每次输入碰到'+'的时候,自增该位置与相应的行和列,当输入结束后,遍历数组,所有为奇数的位置则是操作的位置,而奇数位置的个数之和则是最终的操作次数.”

按照这个只需一个标记数组就行了，标记每个handle是奇数次还是偶数次。16ms AC。