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

题目解析

$i, j ∈ [1,4]$，我们发现为了最优性，每个点至多只可能改变一次状态（指自己影响自己），数据点很小，用状态压缩暴力枚举所有点是否自己影响自己即可

若仍对状态压缩有不理解的地方，请回顾 最短Hamilton路径

#include <cstdio>
#include <cstring>
#include <algorithm>

const int N = 10;
char a[N][N];
int arr[N][N], Vis[N][N], brr[N][N];

void change(int x, int y) {
    brr[x][y] == 1 ? brr[x][y] = 0 : brr[x][y] = 1;
    for (int i = 1; i <= 4; i++) {
        if(i != x) brr[i][y] == 1 ? brr[i][y] = 0 : brr[i][y] = 1;
        if(i != y) brr[x][i] == 1 ? brr[x][i] = 0 : brr[x][i] = 1;
    }
}

int main() {
    for (int i = 1; i <= 4; i++) {
        scanf("%s", a[i] + 1);
    }

    for (int i = 1; i <= 4; i++) {
        for (int j = 1; j <= 4; j++) {
            if(a[i][j] == '-') {
                arr[i][j] = 0;
            } else {
                arr[i][j] = 1;
            }
        }
    }

    //枚举所有点的可能性 1 是改变当前点的状态 0 则是当前点不作出任何改变
    for (int k = 0; k < (1 << 16); k++) {
        memset(Vis, 0, sizeof(Vis));
        int q = 1, p = 0;
        for (int i = 0; i < 16; i++) {
            p++;
            if(i % 4 == 0 && i != 0) q += 1, p = 1;
            if(k >> i & 1) {
                Vis[q][p] = 1;
            } else Vis[q][p] = 0;
        }

        for (int i = 1; i <= 4; i++) {
            for (int j = 1; j <= 4; j++) {
                brr[i][j] = arr[i][j];
            }
        }

        int ans = 0;
        for (int i = 1; i <= 4; i++) {
            for (int j = 1; j <= 4; j++) {
                if(Vis[i][j] == 1) {
                    ans++;
                    change(i, j);
                }
            }
        }

        int flag = 0;
        for (int i = 1; i <= 4; i++) {
            for (int j = 1; j <= 4; j++) {
                if(brr[i][j] == 1) { flag = 1; break; }
            } if(flag == 1) break;
        }

        if(flag == 0) {
            printf("%d\n", ans);
            for (int i = 1; i <= 4; i++) {
                for (int j = 1; j <= 4; j++) {
                    if(Vis[i][j] == 1) {
                        printf("%d %d\n", i, j);
                    }
                }
            }
        }
    } return 0;
}