题目描述
将4 x 4的矩阵全变成‘-’;
对i,j操作一次,其所在的行与列所有灯泡的状态也随之操作为原来的相反(’+’ -> ‘-‘;’-‘->’+’)
求出将矩阵全变为’-‘次数最小值是多少。
输入格式
输入一共包含四行,每行包含四个把手的初始状态。(即输入矩阵)
符号“+”表示把手处于闭合状态,而符号“-”表示把手处于打开状态。
至少一个手柄的初始状态是关闭的。
输出格式
第一行输出一个整数N,表示所需的最小切换把手次数。
接下来N行描述切换顺序,每行输入两个整数,代表被切换状态的把手的行号和列号,数字之间用空格隔开。
注意:如果存在多种打开冰箱的方式,则按照优先级整体从上到下,同行从左到右打开。
数据范围
1≤i,j≤4
样例
输入样例:
-+--
----
----
-+--
输出样例:
6
1 1
1 3
1 4
4 1
4 3
4 4
C++ 代码
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
const int N=5;
char g[N][N],backup[N][N];
int get(int i,int j){
return i*4+j;
}
//也是开关问题,但不能递推,数据范围小,可以暴力枚举每一个方案(二进制:16位即4*4位)
//步骤:
//1.先枚举每个方案(字典序最小:因此只要从0~2^16-1依次枚举方案即可,1表示操作,0表示不操作)
//2.对每个方案进行操作
//3.保存最小的方案,并输出
void turn_one(int i,int j){
if(g[i][j]=='+')g[i][j]='-';
else g[i][j]='+';
}
void turn_all(int x,int y){
for(int i=0;i<4;i++)
{
turn_one(x,i);
turn_one(i,y);
}
turn_one(x,y);
}
int main(){
for(int i=0;i<4;i++)cin>>g[i];
vector<PII>res;
for(int op=0;op< 1<<16;op++){
vector<PII>temp;
memcpy(backup,g,sizeof g);//备份
for(int i=0;i<4;i++)//进行操作
for(int j=0;j<4;j++)
if(op>>get(i,j)&1){
temp.push_back({i,j});
turn_all(i,j);
}
bool has_closed=true;
//判断所有灯泡是否全亮
for(int i=0;i<4;i++)
for(int j=0;j<4;j++)
if(g[i][j]=='+')has_closed=false;
if(has_closed){
if(res.empty()||res.size()>temp.size())res=temp;
}
memcpy(g,backup,sizeof g);//还原
}
cout<<res.size()<<endl;
for(auto op:res){
cout<< op.x+1<<" "<<op.y+1<<endl;
}
return 0;
}