思路:本题是16个开关,每个开关两种状态,也就是2^16的级别,暴力是可以接受的
- 我们用
0~2^16-1
这2^16个数来表示所有的情况,其中每个数都看成一个16位二进制序列,一位对应一个开关,如果该位为1,代表这个开关要按,否则代表不按。(注意1和0不是代表+
或-
,而是代表按或不按) - 每次枚举一个方案时,先用backup来接收初始状态的矩阵,然后就对backup来进行操作和改变,原矩阵st一直不变,用于每次枚举一个新方案时重置backup
- 直接把4行4列的开关用0~15来表示及对应,对每个开关,看看本次操作op在这位上是1还是0,如果是1,代表要按,就
cnt++
,且调用turn()
,turn()
也就是实现全行全列翻转,注意中心位被翻转两次,所以最后还要翻转第3次。 - 遍历完16个开关后,就判断是否全部变为
-
了,如果是,再判断操作次数是否比当前最优解更少,如果是,更新当前最优解,我用两个数组来存储操作的开关的横纵坐标。每次出现最优解时,下标从0开始,覆盖上一次存储的坐标。 - 具体看注释即可
带注释代码
#include <bits/stdc++.h>
using namespace std;
const int N = 5;
char st[N][N], backup[N][N]; // backup数组是每次用来操作变化的
int res = 1e8;
int ans_x[100];
int ans_y[100];
void turn(int x, int y)
{
for(int i = 0;i<4;i++)
{
if(backup[x][i] == '+') backup[x][i] = '-';
else backup[x][i] = '+';
if(backup[i][y] == '+') backup[i][y] = '-';
else backup[i][y] = '+';
}
if(backup[x][y]=='+') backup[x][y] = '-';
else backup[x][y] = '+';
}
int main()
{
for(int i = 0;i<4;i++) cin>>st[i];
// 一共16个位置,1和0代表每个位置按或不按,2^16种情况,暴力枚举所有方案
// 注意1和0不是代表每个位置是+还是-,是代表按还是不按
int n = 1<<16; // 0~2^16-1之间的每一个数,都看成是16位二进制的形式
for(int op = 0;op<n;op++) // 枚举每一种方案
{
memcpy(backup, st, sizeof st); // 每次枚举到一种方案时,重新还原backup数组
int cnt = 0; // 每种方案操作前重置记录按开关的次数
for(int i = 0;i<16;i++) // 按照当前方案,对对应位置的开关进行操作。
{
if(op>>i & 1) // 对应二进制位为1,代表要按下开关,即调用turn()
{
cnt++; // 要按下开关,就要记录次数++
turn(i/4,i%4);
// 比如第5个开关(从0开始,第一行是0123)
// 就在第5/4==1行(从0开始),5%4==1第一列
// 也就是通俗意义上的第二行第二列
/*
0 1 2 3
4 5 6 7
8 ……
*/
}
}
bool flag = false;
for(int i = 0;i<4;i++) // 操作完成后,判断开关是否全是'-'
{
for(int j = 0;j<4;j++)
{
if(backup[i][j] == '+')
{
flag = true;
break;
}
}
if(flag) break;
}
if(!flag)
{
//如果有更小的结果,就更新res,且重新覆盖ans数组
// 而且后续cnt == res的情况是不管的,这就保证了题目要求
// "如果存在多种打开冰箱的方式,则按照优先级整体从上到下,同行从左到右打开。"
if(cnt<res)
{
res = cnt;
int k1 = 0, k2 = 0;
for(int i = 0;i<16;i++)
{
if(op>>i & 1)
{
int x = i/4 + 1;
int y = i%4 + 1;
ans_x[k1++] = x;
ans_y[k2++] = y;
}
}
}
}
}
cout<<res<<endl;
for(int i = 0;i<res;i++) cout<<ans_x[i]<<' '<<ans_y[i]<<endl;
return 0;
}
不带注释代码
#include <bits/stdc++.h>
using namespace std;
const int N = 5;
char st[N][N], backup[N][N];
int res = 1e8;
int ans_x[100];
int ans_y[100];
void turn(int x, int y)
{
for(int i = 0;i<4;i++)
{
if(backup[x][i] == '+') backup[x][i] = '-';
else backup[x][i] = '+';
if(backup[i][y] == '+') backup[i][y] = '-';
else backup[i][y] = '+';
}
if(backup[x][y]=='+') backup[x][y] = '-';
else backup[x][y] = '+';
}
int main()
{
for(int i = 0;i<4;i++) cin>>st[i];
int n = 1<<16;
for(int op = 0;op<n;op++)
{
memcpy(backup, st, sizeof st);
int cnt = 0;
for(int i = 0;i<16;i++)
{
if(op>>i & 1)
{
cnt++;
turn(i/4,i%4);
}
}
bool flag = false;
for(int i = 0;i<4;i++)
{
for(int j = 0;j<4;j++)
{
if(backup[i][j] == '+')
{
flag = true;
break;
}
}
if(flag) break;
}
if(!flag)
{
if(cnt<res)
{
res = cnt;
int k1 = 0, k2 = 0;
for(int i = 0;i<16;i++)
{
if(op>>i & 1)
{
int x = i/4 + 1;
int y = i%4 + 1;
ans_x[k1++] = x;
ans_y[k2++] = y;
}
}
}
}
}
cout<<res<<endl;
for(int i = 0;i<res;i++) cout<<ans_x[i]<<' '<<ans_y[i]<<endl;
return 0;
}