AcWing 95. 费解的开关
原题链接
中等
作者:
ls131
,
2021-02-07 00:39:27
,
所有人可见
,
阅读 509
#include<bits/stdc++.h> //只有开和关 指数型枚举 每个格子最多安一次 按两次等于没按且多步走
using namespace std; //把第一行看作二进制数映射到十进制进行 0-31对应了第一行各种方式 (位运算)
const int N=6; //每一行的各个位置状态由其上唯一确定 最后一行不变成功与否的判定
char g[N][N],backup[N][N]; //把第一行的三十二种所有状态全枚举一遍 目的为了变成全1
//0 1两种不同的含义 第一行是枚举 五个位置各个位置1是按了还是0没按 底下矩阵是亮了还是没亮 min把第一行所有状态取最小值
int dx[]={-1,0,1,0,0},dy[]={0,1,0,-1,0}; //左上右下中心 偏移量
void turn(int x,int y){
for(int i=0;i<5;i++){
int a=x+dx[i],b=y+dy[i];
if(a<0||a>=5||b<0||b>=5) continue; //界外
g[a][b]^=1; //异或 按位取反
}
}
int main(){
int T;
cin>>T;
while(T--){
for(int i=0;i<5;i++) cin>>g[i];
int res=10; //设置一个越界量比对
for(int op=0;op<32;op++){
memcpy(backup,g,sizeof g);// 接下来会改变g数组 提前存储backup辅助数组一会还原g数组 进行32次比较得到最小值
int step=0;
for(int i=0;i<5;i++)
if(op>>i&1){
step++;
turn(0,i); //0 1枚举的是按不按的状态 不是灯亮或者暗
}
for(int i=0;i<4;i++)
for(int j=0;j<5;j++)
if(g[i][j]=='0'){
step++;
turn(i+1,j); // 第二行到倒数第二行哪个位置按由上一行唯一确定
}
bool dark=false; //操作的这一行确保上一行全亮 查看最后一行是否全亮确保方案可行
for(int i=0;i<5;i++) //判断最后一行是否还有亮
if(g[4][i]=='0'){
dark=true;
break;
}
if(!dark) res=min(res,step);
memcpy(g,backup,sizeof g);
}
if(res>6) res=-1;
cout<<res<<endl;
}
return 0;
}
if(op>>i&1)是啥意思啊
晓得了,1~32的每个数对应的二进制是唯一,即1的位置组合也是唯一的,以1所在的位置摁的话,就不会重复,也不会漏,算是一个标识,我觉得不是1表示摁,0表示不摁吧,只是这个1容易表达。
关于数组备份的话,就是为了防止上一次影响下面的枚举
step每次也要重新置0
所以res,step,memcpy的位置都很重要啊
总的来说,就是利用每个十进制对应唯一二进制,1位置组合的唯一性对开关进行不重不漏(第一行)的枚举操作,记下每次的次数,更新最小值,重置次数,重新计数,不能忘记备份
注:我太懒了,就在你这发了,别删奥