题目描述

“飞行员兄弟”这个游戏，需要玩家顺利的打开一个拥有 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

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <climits>
#include <cstring>

using namespace std;

struct node{
    int x, y;
};
char sign[4][4];
int ans = INT_MAX;
vector<node> route;

void change(int x, int y){
    for(int i = 0; i < 4; i++){
        if(y != i){
            if(sign[x][i] == '+') sign[x][i] = '-';
            else sign[x][i] = '+';
        }
        if(sign[i][y] == '+') sign[i][y] = '-';
        else sign[i][y] = '+';
    }
}

void search(int n, vector<node> &troute, int tans){
    char backup[4][4];
    for(int i = 0; i < 1<<4; i++){
        memcpy(backup, sign, sizeof(sign));

        int t = 0, ttans = tans;
        while(i>>t){
            if(i>>t &1){
                change(n, t);
                ttans++;
                troute.push_back(node{n+1,t+1});
            }
            t++;
        }
        if(n == 3){
            bool yes = true;
            for(int x = 0; x < 4; x++){
                for(int y = 0; y < 4; y++){
                    if(sign[x][y] == '+') yes = false;
                }
            }
            if(yes && ttans < ans){
                ans = ttans;
                route = troute;
            }
        }else search(n+1, troute, ttans);

        t = 0;
        while(i>>t){
            if(i>>t &1){
                troute.pop_back();
            }
            t++;
        }
        memcpy(sign, backup, sizeof(backup));
    }
}

int main(){
    int i;
    for(i = 0; i < 4; i++)
        cin >>sign[i];

    vector<node> troute;
    search(0, troute, 0);

    cout <<ans <<endl;
    for(i = 0; i < route.size(); i++) cout <<route[i].x <<" " <<route[i].y <<endl;
    return 0;
}