题目描述

“飞行员兄弟”这个游戏，需要玩家顺利的打开一个拥有16个把手的冰箱。

已知每个把手可以处于以下两种状态之一：打开或关闭。

只有当所有把手都打开时，冰箱才会打开。

把手可以表示为一个4х4的矩阵，您可以改变任何一个位置[i,j]上把手的状态。

但是，这也会使得第i行和第j列上的所有把手的状态也随着改变。

请你求出打开冰箱所需的切换把手的次数最小值是多少。

输入格式
输入一共包含四行，每行包含四个把手的初始状态。

符号“+”表示把手处于闭合状态，而符号“-”表示把手处于打开状态。

至少一个手柄的初始状态是关闭的。

输出格式
第一行输出一个整数N，表示所需的最小切换把手次数。

接下来N行描述切换顺序，每行输入两个整数，代表被切换状态的把手的行号和列号，数字之间用空格隔开。

样例

输入样例:

-+--
----
----
-+--

输出样例:

6
1 1
1 3
1 4
4 1
4 3
4 4

算法

$O(n^2)$

时间复杂度分析：对这个矩阵进行行和列的遍历，所以时间复杂度是$O(n^2)$;
原理分析:首先思路是借鉴某博客大佬的思路，刚开始我的思路是将+-转换为01来进行取反运算求解。但是未找到规律，代码写不出来。于是就借鉴大佬博客来写。首先选中(i,j)元，，其所在的i行j列中的每一个元素都进行翻转，(i,j)翻转了7次，i行j列翻转了４次，其余元素翻转了2次，翻转偶数次其值是不变的，那么变化的就是(i,j)元。通过使用该规律，来求解。

C++ 代码

#include<iostream>

using namespace std;

int I[5][5]　=　{0};//处理
char L[5][5];　//输入
int main()
{
    for(int i=0;i<4;i++)
        for(int j=0;j<4;j++)
            cin　>>　L[i][j];
    for(int i=0;i<4;i++)
    {
        for(int j=0;j<4;j++)
        {
            if(L[i][j]=='+')
            {
                for(int k=0;　k<4;　k++)
                {
                    I[k][j]++;//列
                    I[i][k]++;//行
                }
                I[i][j]--;//上边多加了一次
            }
        }
    }
    int ans=0;
    for(int i=0;i<4;i++)
        for(int j=0;j<4;j++)
            if(I[i][j]%2!=0)
                ans++;
    cout << ans << endl;
    for(int i=0;i<4;i++)
        for(int j=0;j<4;j++)
            if(I[i][j]%2!=0)
                cout<< i+1　<<' '<< j+1 << endl;
    return 0;
}