费解的开关
题目 费解的开关
思路分析
按一个按钮 会引起上下左右以及它本身5个方式变化
我们从第一行开始按起 发现如果第一行的全按过了 第二行就只能根据第一行的状态来决定按不按
（能影响第一行状态的只有它左右下三个按钮 如果第一行按完了 2位置是关 那么第二行的2位置就一定要按 让第一行2位置变成开 反之第一行按完了 1位置的开 那么第二行的1位置就一定不能按）
有一个特性就是 只需要把第一行的所有位置按与不按的情况枚举出来 根据第一行的每一种状态都会唯一确定一种所有棋盘的状态
（第一行决定第二行 第二行决定第三行 直到最后如果第5行没有全变开 就说明有问题）
要注意的是枚举第一行的意义是：不需要在意第一行的灯是灭是暗，只需把第一行的按法枚举一遍，也就是我们说的 “操作”，每个位置都有两种选择，按(用1表示)或者不按(用0表示)，遍历这32种操作引发的情况，每一次再通过res = min(res, step);把最小步数存一下，就能找到最优解 （比如10001代表我们选择按第一行编号为0和编号为4的开关，然后对输入数据中第一行这两位执行turn操作）
如何枚举出32种第一行的操作搭配 其实就是二进制枚举子集的问题 或者用dfs也能写
点击按钮的操作就是让自己和上下左右都反转一下开关
以左上角为中心 往下是x正方向 往右是y正方向
那么对于一个坐标x,y
它本身就是x+0,y+0 下边就是x+1,y+0 右边x+0,y+1 上x-1,y+0 左x+0,y-1
就可以这样实现按下按钮的翻转操作
int dx[5]={0,1,0,-1,0},dy[5]={0,0,1,0,-1};
for(int i=0;i<5;i++){
int xx=x+dx[i],yy=y+dy[i];
if(xx>=0 && xx<5 && yy>=0 && yy<5)
g[xx][yy]^=1;
}
可以发现这其实是个不太明显的递推问题
由第一行的状态递推出所有行的状态 但写法与模版有些大相径庭
大部分也是考察在了二进制枚举子集上
代码实现
#include<bits/stdc++.h>
using namespace std;
const int N = 10;
char g[N][N];
void turn(int x,int y)
{
int dx[5]={0,1,0,-1,0},dy[5]={0,0,1,0,-1};
for(int i=0;i<5;i++)
{
int xx=x+dx[i],yy=y+dy[i];
if(xx>=0 && xx<5 && yy>=0 && yy<5)
g[xx][yy]^=1;
}
}
int work()
{
int ans = 0x3f3f3f3f;
//第一行按灯一共有32种可能，对于每一种可能，我们操作选择后，开始固定，
//此时第一行不一定是全亮的状态，第一行只是32种操作可能的一种
//这一步是枚举第一行的点击方法，只要第一行固定了，那么满足题意的点击方法就只有一种了。
//假如第一行是00111
//k从0到31进行枚举，如果k = 00001，
//那么代表g矩阵中第一行的第一个灯要点击一下，
//第一行变为11111
//k不断变大(0变到31 00001 00010 00011……)
//假如第一行是00111, k从0到31进行枚举，如果k = 10001，
//那么代表g矩阵中第一行的第一个灯和最后一个灯要点击一下，
//第一行变为11100
//之后固定这一行，后面的行都要根据这个确定的第一行而确定 不断往下做 看是否能全变亮
//这也就是为什么我们进行备份, 每一次对k的枚举都会改变light。
for(int k=0;k<(1<<5);k++)
{
int res=0;
char temp[N][N];
memcpy(temp,g,sizeof g);
//根据枚举出的对第一行的操作 对第一行某按钮进行点击
for(int j=0;j<5;j++)
{
if(k>>j & 1)
{
res++;
turn(0,j);
}
}
//后面4行都会因为第一行的确定而确定（每行都根据上一行的确定而确定）
for(int i=0;i<4;i++)
{
for(int j=0;j<5;j++)
{
if(g[i][j]=='0')
{
res++;
turn(i+1,j);
}
}
}
//只需要看第五行是否全是1即可
bool flag=true;
for(int i=0;i<5;i++)
{
if(g[4][i]!='1')
{
flag=false;
break;
}
}
if(flag)
ans = min(ans,res);//更新最少所需步数
memcpy(g,temp,sizeof g);//还原状态
}
if(ans>6)
return -1;
else
return ans;
}
int main()
{
int n;
cin>>n;
while(n--)
{
for(int i=0;i<5;i++)
cin>>g[i];
cout<< work() <<endl;
}
return 0;
}
💬 评论