AcWing 116. 飞行员兄弟--暴力枚举方案
原题链接
简单
作者:
Jocelin
,
2021-04-08 16:10:46
,
所有人可见
,
阅读 528
#include<iostream>
#include<cstring>
using namespace std;
char a[4][4];
char backup[4][4];
void turn(int x,int y)
{
for(int i = 0;i< 4;i++)
{
if( a[x][i] == '+')
a[x][i] = '-';
else
a[x][i] = '+';
}
for(int i = 0;i< 4;i++)
{
if( a[i][y] == '+')
a[i][y] = '-';
else
a[i][y] = '+';
}
if( a[x][y] == '+')
a[x][y] = '-';
else
a[x][y] = '+';
}
int main()
{
for(int i = 0; i < 4;i++)
{
cin >> a[i];
}
// for(int i = 0; i < 4;i++)
// {
// for(int j = 0; j < 4;j++)
// cout << a[i][j] << " ";
// cout << endl;
// }
memcpy(backup,a,sizeof a);
int res = 1000;
int res_op = 0;
for(int op = 0 ; op < 65536;op++) //我们枚举所有的方案数,
//一共16个格子,所以所有的方案也即是2^16 = 65536,我们用他的二进制表示选某一位
{
int cnt = 0;
for(int i = 0; i <16;i++)
{
if( (op >> i) & 1 ) //取出枚举的数所有位的二进制,如果当前按的话我们改变一下状态
{
cnt++;
int x = i / 4;
int y = i % 4;
turn(x,y);
}
}
bool flag = true;
for(int i = 0; i < 4;i++)
{
for(int j = 0; j < 4;j++)
if(a[i][j] == '+')
{
flag = false;
break;
}
}
if( flag == 1)
{
res = min(cnt,res);
res_op = op; //我们把最后这个数存下来,因为我们直接通过这个数的二进制表示,坐标转化一下就得到答案了
}
memcpy(a,backup,sizeof a); //记得每次恢复到原来的状态,重新枚举
}
cout << res << endl;
for(int i = 0; i <16;i++)
{
if( (res_op >> i) & 1 )
{
cout << i / 4 + 1<< " " << i % 4 + 1 << endl;
}
}
// cout << res_op << endl;
return 0;
}
为什么要初始化res=1000呢 没太看明白,直接输出res的大小有问题吗