算法1
思路:这个题整体还是有点难,我们的目标是把4*4的二维数组中的+全部变成-,按照步数最小,字典序最小输出出来
1.枚举所有方案,一共有1~2^16-1个,下面写的时候可以写成1<<16-1
2.按照该方案,对所有数进行操作
3.进行判断,利用res记录方案
C++ 代码
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
typedef pair<int,int> PII;
#define x first
#define y second
const int N=5;
char g[N][N],backup[N][N];
int get(int x,int y){
return x*4+y;//返回第x行,第y列上的数是多少
}
void turn_one(int x,int y){
if(g[x][y]=='+')g[x][y]='-';
else g[x][y]='+';
}
void turn_all(int x,int y){//把所有数都转换一遍
for(int i=0;i<4;i++)
{
turn_one(x,i);//把第x行第i个数turn一遍
turn_one(i,y);//把第i行第y个数都turn一遍
}
turn_one(x,y);//因为x,y都turn了两遍,所以需要再次turn一遍,去抵消一遍
}
int main(){
for(int i=0;i<4;i++)cin>>g[i];
vector<PII> res;//记录方案用
for(int op=0;op<1<<16;op++)//步骤一,1左移16位,就是2^16
{
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)//如果当前位置是1
{
temp.push_back({i,j});//temp里面存的是方案
turn_all(i,j);//按一下开关
}
//判断所有灯泡是否全亮
bool has_closed=false;//一开始亮
for(int i=0;i<4;i++)
for(int j=0;j<4;j++)
if(g[i][j]=='+')
has_closed=true;
if(has_closed==false){
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;//我们的下标是从0,开始的,这里对x,都要加1
return 0;
}