AcWing 116. 飞行员兄弟
原题链接
简单
作者:
Me_32
,
2024-01-16 22:26:06
,
所有人可见
,
阅读 51
#include<bits/stdc++.h>
using namespace std;
char state[10][10],temp[10][10];//state存放初态,temp存放副本
int res=INT_MAX;//存放操作次数
vector<pair<int,int>>v;//记录最优解
vector<pair<int,int>>t;//记录操作步骤
void turn(int x,int y){//改变x行y列的值
for(int i=0;i<4;i++){
if(temp[i][y]=='+')temp[i][y]='-';
else temp[i][y]='+';
if(i!=y){
if(temp[x][i]=='+')temp[x][i]='-';
else temp[x][i]='+';
}
}
}
//检查该方案最终得到的结果是否正确
bool check(){
for(int i=0;i<4;i++){
for(int j=0;j<4;j++){
if(temp[i][j]=='+')return false;
}
}
return true;
}
int main(){
for(int i=0;i<4;i++)cin>>state[i];
for(int i=0;i<(1<<16);i++)//枚举16个开关所有可能的情况,对应二进制位为1,则操作该开关
{
int step=0;
memcpy(temp,state,sizeof state);//拷贝副本
for(int j=0;j<16;j++){
if(i>>j&1){
step++;
int x=j/4,y=j%4;//得到行号,列号
t.push_back({x+1,y+1});
turn(x,y);
}
}
if(check()){
if(step<res){
res=step;v=t;
}
}
t.clear();
}
cout<<res<<endl;
for(auto i : v){
cout<<i.first<<" "<<i.second<<endl;
};
return 0;
}