题目描述

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

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

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

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

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

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

输入格式

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

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

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

输出格式

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

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

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

数据范围

$1 \le i,j \le 4$

输入样例：

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

输出样例：

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

算法

暴力枚举

write here…

时间复杂度

$O(n^2)$
write here…

空间复杂度

write here…

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int N =6;
int minor=17,seq;//教训就是把N和minor取大一点，比正常大2最好
char ice[N][N],backup[N][N];
void shift(int x,int y){
    for(int i=0;i<4;i++)if(i!=x)ice[i][y]='-'+'+'-ice[i][y];
    for(int j=0;j<4;j++)ice[x][j]='-'+'+'-ice[x][j];
}
int main() {
    for(int i=0;i<4;i++)cin>>ice[i];
    memcpy(backup,ice,sizeof(ice));
    for(int i=0;i<1 << 16;i++){
        bool val=true;int cnt=0;
        memcpy(ice,backup,sizeof(ice));
        for(int j=0;j<4;j++)
            for(int k=0;k<4;k++)
                if(i>>(4*j+k)&1){shift(j,k);cnt++;}
        for(int j=0;j<4;j++)
            for(int k=0;k<4;k++)
                if(ice[j][k]=='+')val=false;
        if(val&&cnt<minor)
            minor=cnt,seq=i; 
    }
    cout<<minor<<endl;
    for(int j=0;j<4;j++)
            for(int k=0;k<4;k++)
                if(seq>>(4*j+k)&1)cout<<j+1<<' '<<k+1<<endl;
}