感谢楼下@fashoint大佬指出本题不严谨的错误,以及数据过水问题.
估计不久后,就会添加Hack数据,各位大佬们,不用惊慌.

题目描述

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

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

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

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

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

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

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

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

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

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

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

数据范围
1≤i,j≤4
输入样例：

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

输出样例：

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

注意：如果存在多种打开冰箱的方式，则按照优先级整体从上到下，同行从左到右打开。
感谢ACwing翻译

算法1

(暴力枚举) O(n^16)

每一次枚举，选择任何一个点

正解

算法标签：位运算+二进制枚举

解题思路：这道题目解题思路大致是，首先我们可以构造一个16位的二进制数，然后呢，二进制数的每一位代表4*4矩阵中的一位，例如1代表(1,1),2代表(1,2),3代表(1,3),4代表(1,4),5代表(2,1)。既然这样的话，那么我们只需要枚举这个16位的二进制数，就可以确定我们的方案，因为题目只需要最优解方案，所以时间复杂度大约是O(16 * 2^16)

代码略丑，不要在意

C++ 代码

//数据太水,那个ok剪枝不成立,请自动删去,并添加min函数,找最小把手值.
#include <bits/stdc++.h>
using namespace std;
int a[21][21],i,j,k;
queue<pair<int,int> > ans2,ans1;
queue<pair<int,int> > kong; //空序列，用于清空序列 
int main()
{
    char ch;
    for (i=1; i<=4; i++)
    {
        for (j=1; j<=4; j++)
        {
            ch=getchar();
            if (ch=='-')
                a[i][j]=1;
        }
        getchar();
    }
//  cout<<c[1]<<endl<<c[2]<<endl<<c[3]<<endl<<c[4]<<endl;
    int ans=1e7;
    for (i=1; i<(1<<17); i++)
    {
        int b[5][5];
        for (j=1; j<=4; j++)
            for (k=1; k<=4; k++)
                b[j][k]=a[j][k];
        ans1=kong;
        for (j=1; j<=16; j++)
            if (i>>(j-1) & 1)
            {
                int dx=j%4,dy=j/4+1;
                if (j%4==0)
                    dx=4,dy--;
                for (k=1;k<=4;k++)
                    b[dy][k]^=1;
                for (k=1;k<=4;k++)
                    if (k!=dy)
                        b[k][dx]^=1;
                ans1.push(make_pair(dy,dx));
            }
        bool ok=true;
        for (j=1;j<=4;j++)
            for (k=1;k<=4;k++)
                if (!b[j][k])
                    ok=false;
        if (ok)
            break;
    }
    cout<<ans1.size()<<endl;
    while(!ans1.empty())
    {
        cout<<(ans1.front()).first<<" "<<ans1.front().second<<endl;
        ans1.pop();
    }
    return 0;
}