翻转问题的做法及其他例题

题目描述

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

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

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

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

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

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

输入格式

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

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

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

输出格式

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

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

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

样例

输入：

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

输出：

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

因为这是翻转问题，所以冰箱的每个把手最多只可转一次（转两次相当于没转）

所以直接枚举所有冰箱的把手情况即可：共16^2种情况（65,536）（在控范围内）

算法:

(暴力枚举)

# include<iostream>
# include<algorithm>
# include<cstring>
# include<set>

using namespace std;

const int N = 9;

int g[N][N], b[N][N];
char k[N][N];
set<pair<int, int>> res1, res2;     //set用来存路径（一个存当前路径，一个存答案路径）

void op(int x, int y)               //翻转操作（用偶数来表示开，奇数表示关）
{
    for(int i=0; i<4; ++i)
    {
        b[x][i]++;
        b[i][y]++;
    }
    b[x][y]--;
}

bool ck()                           //检查一下答案是否正确
{
    for(int i=0; i<4; ++i)
        for(int j=0; j<4; ++j)
            if(b[i][j] & 1)   return false;

    return true;
}

int main()              //偶数为开，最终要全开
{
    int ans = 1111;

    for(int i=0; i<4; ++i)      //用0，1来表示+，-我个人感觉会方便一些
    {
        for(int j=0; j<4; ++j)
        {
            cin>>k[i][j];
            if(k[i][j]=='+')   g[i][j] = 1;
            else   g[i][j] = 0;
        }
    }

    //用二进制直接枚举每行每列的所有情况
    for(int i=0; i<(1<<4); ++i)
    {
        for(int j=0; j<(1<<4); ++j)
        {
            for(int k=0; k<(1<<4); ++k)
            {
                for(int l=0; l<(1<<4); ++l)
                {
                    int cnt = 0;
                    res1.clear();               //将当前路径清除
                    memcpy(b, g, sizeof g);     //备份所有把手的初始状况
                    for(int p=0; p<4; ++p)
                    {
                    //判断每一行，每一列的情况
                        if((i>>(3-p)) & 1)   {op(0, p);  cnt++;  res1.insert({0+1, p+1});}
                        if((j>>(3-p)) & 1)   {op(1, p);  cnt++;  res1.insert({1+1, p+1});}
                        if((k>>(3-p)) & 1)   {op(2, p);  cnt++;  res1.insert({2+1, p+1});}
                        if((l>>(3-p)) & 1)   {op(3, p);  cnt++;  res1.insert({3+1, p+1});}

                        if(ck() && cnt < ans)   //记录并更新答案
                        {
                            ans = cnt;
                            res2.clear();
                            for(auto t : res1)
                                res2.insert(t);
                        }
                    }
                }
            }
        }
    }
    //输出答案
    cout<<ans<<endl;
    for(auto t : res2)
        cout<<t.first<<' '<<t.second<<endl;

    return 0;
}