AcWing 116. 飞行员兄弟
原题链接
简单
作者:
林小鹿
,
2020-08-15 23:36:32
,
所有人可见
,
阅读 541
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
char g[5][5],backup[5][5];
typedef pair<int ,int >PII; //相当于包含两个元素的结构体
int get(int x,int y) //二维转一维
{
return x*4+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(i,y); //一列
turn_one(x,i); //一行
}
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++) //遍历所有操作 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表示按下,为0不用操作
{
temp.push_back({i,j});
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)
{
if(res.empty()||res.size()>temp.size()) res=temp; //更新答案
}
memcpy(g, backup, sizeof g); // 还原
}
cout<<res.size()<<endl;
for(auto op:res) cout<<op.first+1<<' '<<op.second+1<<endl;
return 0;
}