AcWing 116. 飞行员兄弟
原题链接
简单
作者:
chais
,
2023-12-06 20:15:07
,
所有人可见
,
阅读 43
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
char arr[6][6];
char backup[6][6];
bool check()//检测是否通过
{
bool isok=true;
for(int i=1;i<=4;i++)
for(int j=1;j<=4;j++)
if(arr[i][j]=='0')
isok=false;
if(isok==true)
return true;
else
return false;
}
void turn(int x,int y)//进行按动
{
for(int i=1;i<=4;i++)
{
if(arr[x][i]=='0')
arr[x][i]='1';
else
arr[x][i]='0';
}
for(int i=1;i<=4;i++)
{
if(arr[i][y]=='0')
arr[i][y]='1';
else
arr[i][y]='0';
}
if(arr[x][y]=='1')
arr[x][y]='0';
else
arr[x][y]='1';
}
int main()
{
for(int i=1;i<=4;i++)
for(int j=1;j<=4;j++)
{
char x;
cin>>x;
if(x=='-')
arr[i][j]='1';
else
arr[i][j]='0';
}
//枚举,共2^16种情况,底数2对应按或者不按两种情况,指数16代表16个拉杆,
int res=16;
pair <int,int> respair[16];//用于记录情况最少的按动过程
for(int op=0;op<65536;op++)//一共2^16中情况,op的二进制数中为0的选择不按,1的按
//同时op的第0位(最左边那位)对应4*4矩阵的[1][1]坐标,第15位对应[4][4]坐标
{
memcpy(backup,arr,sizeof arr);//进行备份
int step=0;
pair<int,int> cs[16];//记录当前op的按动情况
for(int i=0;i<16;i++)//i指示op二进制的位数
{
if(op>>i&1)//op二进制为1的位选择按
{
int x=i/4+1;
int y=i%4+1;//对应关系
turn(x,y);
cs[step]={x,y};
step++;
}
}
if(check()==false)
{memcpy(arr,backup,sizeof arr);//读档
continue;}
memcpy(arr,backup,sizeof arr);//读档
res=min(res,step);
for(int i=0;i<step;i++)//将本次op的按动过程导入respair
respair[i]=cs[i];
}
cout<<res<<endl;
for(int i=0;i<res;i++)
cout<<respair[i].first<<" "<<respair[i].second<<endl;
return 0;
}