AcWing-116-飞行员兄弟

问题

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

using namespace std;
char g[4][5], back[4][5];

//统计整数的二进制包含的　１　的个数
int get_one_bit_count(int x) {
    int count = 0;
    while (x) {
        count++;
        x = x & (x - 1);
    }
    return count;
}

//翻转位置（i, j）
void change(int a, int b) {
    for (int k = 0; k < 4; ++k) {
        g[k][b] = g[k][b] == '+' ? '-' : '+';
        g[a][k] = g[a][k] == '+' ? '-' : '+';
    }
    g[a][b] = g[a][b] == '+' ? '-' : '+';
}

//判断是否全部打开
bool check() {
    for (int i = 0; i < 4; ++i) {
        for (int j = 0; j < 4; ++j) {
            if (g[i][j] == '+') return false;
        }
    }
    return true;
}

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

    memcpy(back, g, sizeof(g));

    int pos = 0, min_cnt = 17;
    for (int k = 0; k < (1 << 17); ++k) {
        int bit_cnt = get_one_bit_count(k);
        if (bit_cnt >= min_cnt) continue;   //操作步数大于等于当前最小步数，则跳过，没必要执行后续操作

        for (int i = 0; i < 4; ++i) {
            for (int j = 0; j < 4; ++j) {
                int p = i * 4 + j;
                if (k >> p & 1) {   //判断 k 的第 p 位是否为 1 
                    change(i, j);
                }
            }
        }

        if (check()) {
            min_cnt = bit_cnt;
            pos = k;
        }
        memcpy(g, back, sizeof(back));  //状态恢复
    }

    cout << min_cnt << endl;
    for (int i = 0; i < 4; ++i) {
        for (int j = 0; j < 4; ++j) {
            int p = i * 4 + j;
            if (pos >> p & 1) cout << i + 1 << " " << j + 1 << endl;
        }
    }

    return 0;
}