题目：poj1753 Flip Game Time:1000MS Mem:65536K 遍历基础题第二题
描述：一个冰箱有4*4矩阵排列的一共16个把手(handles)，每个把手只有'+'(关)和'-'(开)两种状态，当且仅当开关全部为'-',也即冰箱把手都为开启状态的时候冰箱才能被打开。搬动冰箱把手定义一种翻转，即：每次随机选取一个把手翻动，则其所在行和所在列的一共7个把手全部翻转。现在给出16个把手的初始状态（至少有一个把手为'+'），求至少翻动多少轮次，才能够把冰箱门打开，也即把手状态全部为'-'。
输出：达到冰箱开启，即全部把手状态为'-'的最小轮次。首行输出轮次，以下每行输出按次翻动的把手的行号和列号（之间用随意多个空格隔开即可）。
类别：BFS（加标记）|| DFS || 数学巧法，刚刚完成了数学方法的AC，另外两种方法还在尝试。
分析：这道题其实和之前拿到1753差不多个意思，都是在4*4矩阵中转变元素状态（0或1），最终达到全0或全1为止。但这道题我又可耻地在网络的指点之下找到了便捷的数学巧法。感觉自己说起来没有原文清楚...所以还是在此将原文quote一下：
证明:要使一个为'+'的符号变为'-',必须其相应的行和列的操作数为奇数;可以证明,如果'+'位置对应的行和列上每一个位置都进行一次操作,则整个图只有这一'+'位置的符号改变,其余都不会改变. > 设置一个4*4的整型数组,初值为零,用于记录每个点的操作数,那么在每个'+'上的行和列的的位置都加1,得到结果模2(因为一个点进行偶数次操作的效果和没进行操作一样,这就是楼上说的取反的原理),然后计算整型数组中一的个数即为操作数,一的位置为要操作的位置(其他原来操作数为偶数的因为操作并不发生效果,因此不进行操作)...在这种方法中，我不需要在迷茫中继续对4*4矩阵中的每一个元素做16种翻转情况的遍历了，而仅仅需要对初始状态时为'+'的(i, j)元素，以及所有第i行 && 第j列的其余6个元素进行题设中所定义的翻转，再将其状态仍为奇数的元素提取出来，其个数即为所需翻动的轮次，其行列坐标的序列，即为翻动的序列。而由于此题目暗含一定有解（虽然小白我真心不知道怎么证，只是感觉上认同），所以所有情况都已经考虑完全。下面贴上代码：
#include<stdio.h> #include<iostream> bool value[4][4]; int step[2][16] = {0}; int main() { int i, j, m = 0, n = 0; char ch; int count = 0; memset(value, 0, sizeof(value)); for (i = 0; i < 4; i++){ //add the value of every node that is '+' for (j = 0; j < 4; j++){ scanf("%c", &ch); if (ch == '+') { value[i][j] = !value[i][j]; for (m = 0; m < 4; m++){ value[m][j] = !value[m][j]; value[i][m] = !value[i][m]; } } } getchar(); //**very important when scanf(%c) show up } for (i = 0; i < 4; i++){ for (j = 0; j < 4; j++){ if (value[i][j] == true){ step[0][count] = i + 1; step[1][count] = j + 1; count++; } } } printf("%d\n", count); for (i = 0; i < count; i++){ printf("%d %d\n", step[0][i], step[1][i]); } return 0; }错误总结：
1. 由于POJ和VS2010在编译C语言时候的区别，我注意到了bool型的数组不能用 s[n] = {0} || s[n] = {false}来初始化，在vs中没有报错，在poj中会有compile error，必须用C++中的<iostream>中的memset函数做初始化，但初始值可以为 0。还有就是int数组元素不能和true进行==比较。
2. scanf()获取字符多维数组的问题，在换行的时候换行符会被当做一个字符传入数组，必须在一行输入完毕之后用getchar()将换行符"吃掉"，才不会影响矩阵内的元素排列。
3. 在这种状态只有0或1转换问题中，利用bool型元素的！运算，可以省去int型元素在累加多次之后还要进行%2运算的复杂，以后可以留意稍加利用。
4. 这次又犯了马虎的错误，getchar()那个问题要是早些解决可以提前至少两天解决问题，蛋疼。
初入算法门，有些概念和解释逻辑不是很清晰，希望大家不吝赐教。
转载于:https://www.cnblogs.com/wynemo/archive/2013/01/16/2863297.html
相关资源：poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告