0 题目来源

acwing

1 涉及的知识点

指数型枚举、递归、暴搜

指数型枚举：
见递归实现指数型枚举题目
注意指数型枚举不需要for循环。

2 题目描述

“飞行员兄弟”这个游戏，需要玩家顺利的打开一个拥有 1616 个把手的冰箱。
已知每个把手可以处于以下两种状态之一：打开或关闭。
只有当所有把手都打开时，冰箱才会打开。
把手可以表示为一个 4×4的矩阵，您可以改变任何一个位置 [i,j][i,j] 上把手的状态。
但是，这也会使得第 ii 行和第 jj 列上的所有把手的状态也随着改变。
请你求出打开冰箱所需的切换把手的次数最小值是多少。

3 输入输出

输入格式：
输入一共包含四行，每行包含四个把手的初始状态。
符号 + 表示把手处于闭合状态，而符号 - 表示把手处于打开状态。
至少一个手柄的初始状态是关闭的。
输出格式：
第一行输出一个整数 NN，表示所需的最小切换把手次数。
接下来 NN 行描述切换顺序，每行输出两个整数，代表被切换状态的把手的行号和列号，数字之间用空格隔开。
注意：如果存在多种打开冰箱的方式，则按照优先级整体从上到下，同行从左到右打开。
数据范围：
1≤i,j≤41≤i,j≤4

4 样例

输入样例：
-+—
——
——
-+—
输出样例：
6
1 1
1 3
1 4
4 1
4 3
4 4

5 思路

由于本题中改变一个开关，会导致一行一列的开关变化，变化的范围较大，使用递推不太现实。
因此，我们可以直接对44的地图进行暴力搜索。
共有44=16个开关，每个开关有选或不选两种情况，因此总共有种情况，暴搜是完全可以的。
对16个开关进行二元遍历，是典型的指数型枚举，采用递归实现。注意递归实现指数型枚举的形式（没有for循环）
本题中为了方便检测开关是否全部打开，采用opennum变量对开关打开数目进行记录，并在改变开关状态的过程中随时记录。

6 代码

#include<iostream>
#include<string>
#include<vector>
using namespace std;
struct xy
{
    int x, y;
};
string str[4];
int opennum;//记录打开开关的数目
int minstep = 1000000;
vector<xy> vecxy;
vector<xy> finalvec;
void exc(int x, int y)//改变开关状态
{
    for (int i = 0; i < 4; i++)
    {
        if (str[x][i] == '+')
        {
            str[x][i] = '-';
            opennum++;
        }
        else
        {
            str[x][i] = '+';
            opennum--;
        }
        if (i != x)//避免中间开关被重复改变
        {
            if (str[i][y] == '+')
            {
                str[i][y] = '-';
                opennum++;
            }
            else
            {
                str[i][y] = '+';
                opennum--;
            }
        }
    }
}
void dfs(int u,int s)
{
    if (u == 16)
    {
        if (opennum == 16 && s < minstep)
        {
            minstep = s;
            finalvec = vecxy;
        }
        return;
    }
    int j = u % 4;
    int i = u / 4;
    xy temp;
    temp.x = i + 1;
    temp.y = j + 1;
    vecxy.push_back(temp);
    exc(i, j);
    dfs(u + 1, s + 1);//选
    vecxy.pop_back();
    exc(i, j);
    dfs(u + 1, s);//不选
}
int main()
{
    for (int i = 0; i < 4; i++)
    {
        cin >> str[i];
        for (int j = 0; j < 4; j++)
        {
            if (str[i][j] == '-')
                opennum++;
        }
    }
    dfs(0, 0);
    cout << minstep << endl;
    for (int i = 0; i < finalvec.size(); i++)
    {
        cout << finalvec[i].x << ' ' << finalvec[i].y << endl;
    }
    return 0;
}