题意：总共有3x3盏灯，每次切换一个灯还会同时改变上下左右的灯，问想把灯全部打开最少需要操作多少次
输入：一个3X3的矩阵
分析：操作顺序对题目是不影响的，另外，操作奇数次等价于1次，偶数次等价于2次，也就是说最大操作次数是9次
分析题目我们可以发现题目数据规模并不大，可以暴力枚举，并且灯只有开和关两种状态，可以分别用1,0来表示
暴力枚举就是其实就相当于枚举9个元素的全部子集个数，也就是2^9即1<<9
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int inf=1<<30; 4 typedef long long ll; 5 const double pi=acos(-1); 6 const int mod=2000120420010122; 7 const int maxn=2e5+7; 8 int a[3][3],b[3][3]; 9 int main(){ 10 for(int i=0;i<3;i++){ 11 for(int j=0;j<3;j++) 12 scanf("%d",&a[i][j]); 13 } 14 int ans=10; 15 for(int x=0;x<(1<<9);x++){ 16 int cnt=0; 17 for(int i=0;i<3;i++) 18 for(int j=0;j<3;j++) 19 b[i][j]=0;//对b数组初始化别忘记了 20 for(int i=0;i<9;i++){ 21 if(x&(1<<i)){//表示这时候要开第i个灯 22 cnt++;//开灯个数+1 23 int p=i/3,q=i%3; 24 b[p][q]^=1; 25 if(p!=0) b[p-1][q]^=1; 26 if(p!=2) b[p+1][q]^=1; 27 if(q!=0) b[p][q-1]^=1; 28 if(q!=2) b[p][q+1]^=1; 29 } 30 } 31 bool flag=true; 32 for(int i=0;i<3;i++){ 33 for(int j=0;j<3;j++){ 34 if(!(a[i][j]^b[i][j])) flag=false;//只有当ab为11或00时才会为负 35 } 36 } 37 if(flag) ans=min(ans,cnt); 38 } 39 cout<<ans<<endl; 40 return 0; 41 }