AcWing 116. 飞行员兄弟
原题链接
简单
作者:
月亮事务所
,
2021-01-15 22:40:45
,
所有人可见
,
阅读 279
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef pair<int,int>PII;
int change[4][4];
int get(int x,int y)
{
return x*4+y;
}
int main()
{
int state=0;
for(int i=0;i<4;i++)
{
string line;
cin>>line;
for(int j=0;j<4;j++)
if(line[j]=='+') state +=1<<get(i,j);
}
for(int i=0;i<4;i++)
for(int j=0;j<4;j++)
{
for(int k=0;k<4;k++)
{
change[i][j] +=1<<get(i,k);
change[i][j] +=1<<get(k,j);
}
change[i][j] -= 1 << get(i,j);
}
}
vector<PII> res;
for(int k=0;k<1<<16;k++)
{
int now=state;
vector<PII> path;
for(int i=0;i<16;i++)
if(k>>i&1)
{
int x=i/4,y=1%4;
now^=change[x][y];
path.push_back({x,y});
}
if(|now && (res.empty())||res.size()>path.size()) res=path;
}
cout <<res.size()<<endl;
for(auto p:res)cout<<p.first+1<<' '<<p.second+1<<endl;
return 0;