题目描述
“飞行员兄弟”这个游戏,需要玩家顺利的打开一个拥有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
算法1
C++ 代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
using namespace std;
char a[10][10],b[30][30];
typedef pair<int,int> PII;//防止代码过长
#define x first
#define y second
void turn_one(int i,int j){//变,+变-,-变+
if(a[i][j]=='+') a[i][j]='-';
else a[i][j]='+';
}
void turn(int x,int y){
for(int i=0;i<4;i++){
turn_one(x,i);
turn_one(i,y);
}
turn_one(x,y);//x行变完,y列变完。对(x,y)坐标变换了两次相当于没换,所以要在变换一次
}
void work(){
vector<PII> temp;
for(int k=0;k<(1<<16);k++){
//枚举,费解的开关是值对第一行进行枚举,1代表按,0代表不按,
//费解的开关,上面那一行一旦变完就不会再变了,但是此题不同
//是整行整列的变换,只能对16个开关操作遍历,0~1>>16指所有16位2进制数
vector<PII> res;//存的都是转变了哪些坐标的开关了
memcpy(b,a,sizeof(a));
int success=1;//成功的时候
for(int i=0;i<4;i++){
for(int j=0;j<4;j++){
if(k>>(4*i+j)&1){
turn(i,j);
res.push_back({i,j});
}
}
}
for(int i=0;i<4;i++){//看看是否成功了,遍历16个开关看看是否还有闭合的,全部打开-才是成功的
for(int j=0;j<4;j++){
if(a[i][j]=='+'){
success=0;//不成功
}
}
}
if(success){
if(temp.size()>res.size()||temp.empty()) temp=res;
}
memcpy(a,b,sizeof(b));//恢复
}
cout<<temp.size()<<endl;
for(int i=0;i<temp.size();i++){
cout<<temp[i].x+1<<" "<<temp[i].y+1<<endl;
}
}
int main(){
for(int i=0;i<4;i++){
cin>>a[i];
}
work();
return 0;
}