这种题较少见也较难想
按一个开关，会影响上下左右四个方向的数
先可以考虑，只有一排灯的情况
那么一排灯的情况，只有32种按法即(2^5)次，可以用(1~32)每个数的二进制数表示方案，1表示改变灯，0表示不变
如果有两排灯了？是不是感觉有点不知所措
容易发现，改变第一排灯的状态，那么一定会改变第二排灯的状态，所以说，第一次灯的所有方案都试一遍，如果能使整个矩阵亮，那就说明，具有可行方案（但操作次数必须小于等于6），但是你会想为什么不又改变第二排的状态了？其实这时如果第二排的状态改变，那么第一排也会改变，这也相当于第一排改变第二排，所以不用考虑
那么有三排了？
我们还是按照一排灯的情况按一遍一排灯，通过第二排，我们其实可以把第一排灯全变为亮的，第一排某个灯的下一行的灯，通过第三排也可以把第二排灯全亮
，但第三排无法被其他排改变（如果通过第二排改变第三排，不是又舍本求末了吗？）
综上所以可以 第一排逐个方案尝试，然后通过后一排，改变前一排，再判断最后一排是否全亮，记录每次的次数，然后取min
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int t;const int maxn=7;
int res=9;
bool mp[maxn][maxn];
bool mpb[maxn][maxn];
void turn(int x,int y){//改变x,y灯和相邻灯的状态
mp[x][y]^=1;
mp[x+1][y]^=1;
mp[x][y+1]^=1;
mp[x-1][y]^=1;
mp[x][y-1]^=1;
}
int work(){
for(int i=1;i<=5;++i) for(int j="1;j<=5;++j)" mpb[i][j]="mp[i][j];//备份原数组" k="0;k<(1<<5);++k){//二进制为一种方案" int ans="0;" if(k>>(j-1) & 1) {//改变那些灯的状态
++ans;
turn(1,j);
}
for(int i=1;i<=4;++i) for(int j="1;j<=5;++j){" if(mp[i][j]="=0)" { ++ans; turn(i+1,j); } bool flag="0;" i="1;i<=5;++i)" if(mp[5][i]="=0)" if(!flag) res="min(res,ans);//如果可以全亮" mp[i][j]="mpb[i][j];//复原数组" if(res<="6)" cout<<res<<endl; else cout<<"-1"<<endl; int main(){ cin>>t;
while(t--){
res=9;char ch=getchar();
for(int i=1;i<=5;++i) for(int j="1;j<=5;++j){" char c;cin>>c;
mp[i][j]=c-'0';
}
work();
}return 0;
}
</=5;++i)></=4;++i)></=5;++i)></iostream></cstring></cstdio>
ZFY AK IOI
Original: https://www.cnblogs.com/guiyou/p/15186329.html
Author: 归游
Title: 费解的开关
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/584592/
转载文章受原作者版权保护。转载请注明原作者出处！