原题链接
https://www.acwing.com/problem/content/description/118/
题目描述
“飞行员兄弟”这个游戏，需要玩家顺利的打开一个拥有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
注意：如果存在多种打开冰箱的方式，则按照优先级整体从上到下，同行从左到右打开。
算法
思路
此题题意酷似 acwing 95. 费解的开关 https://www.acwing.com/problem/content/97/
不同之处便是状态连锁改变不同，但做法截然不同，此题是一个4*4的矩阵，
暴力枚举的复杂度是 O( 10^7 ), (2^16 * 16 * 16 = 16,777,216) ,10^7的复杂度可以通过此题。
但费解的开关一题 为5 * 5 的矩阵，所以不可以暴力枚举
枚举每个把手拉或不拉，每种拉完后的结果用二进制数k来表示（状态压缩），4*4个把手编号为0~15，输出时为（i/4+1，i%4+1）。
……具体细节看代码吧
时间复杂度
O( 10^7 ) , 2^16 * 16 * 16 = 16,777,216
C++ 代码
#include<iostream>
#include<cstring>
using namespace std;
char c[4][4];
//目的：全部为'-'
int ans=16;//答案
int ansk=(1<<16)-1;//答案状态
void ch(char &c)//拉动单个把手
{
if(c=='+') c='-';
else c='+';
}
void trun(int x,int y)//连锁状态的改变
{
for(int i=0;i<4;i++)
{
ch(c[i][y]);
ch(c[x][i]);
}
ch(c[x][y]);
}
void dfs(int u,int res,int k)//u表示当前编号，res表示已经拉动的个数，k表示二进制下的状态（一个16位的二进制数）
{
if(u>15)//遍历完一遍
{
bool is_true=1;
//判断是否合法
for(int i=0;i<4;i++)
for(int j=0;j<4;j++)
if(c[i][j]=='+')//不合法
{
is_true=0;
break;
}
if(is_true==1)
{
if(res<ans)//更新答案,注意ansk也要更新
{
ans=res;
ansk=k;
}
}
return ;
}
int x=u/4,y=u%4;//行为u/4,列为u%4
trun(x,y);
res++;
k+=1<<u;
dfs(u+1,res,k);//拉动此把手
trun(x,y);
res--;
k-=1<<u;
//还原现场
dfs(u+1,res,k);//不拉动次把手
}
void nout()
{
cout<<ans<<endl;
for(int i=0;i<16;i++)
{
if(ansk>>i&1)//如果第i位为1，表示拉动了
{
cout<<i/4+1<<" "<<i%4+1<<endl;
//注意：因为答案行列的编号从1~4，而我们存的是0~3，所以记得+1
}
}
}
int main()
{
for(int i=0;i<4;i++) cin>>c[i];//读入
dfs(0,0,0);//从第0个开始枚举，已经拉动了0次，状态为0（什么都没拉）
nout();//输出
return 0;
}
求赞
本蒟蒻第一次写题解，如有问题请诸位dalao指正
给个赞吧
标签：状态,进阶,16,题解,t1,枚举,把手,打开,acwing From： https://www.cnblogs.com/yingxilin/p/17625575.html