D wyh 关灯
#include<bits/stdc++.h> using namespace std; int m, n=7, a,ko=0,lk=0; int l[17]= {0}; int temp[17]= {0}; int yu[100025]= {0}; int pk[11]= {0},kp[11]= {0}; int sum=101; int bcount(unsigned int n) { int count; for(count=0; n; n>>=1) { count+=n&1; } return count; } void out(int k) { if(yu[k]==((1<<(n+1))-1)) return; int ui=1; for (int i = 0; i < 17; i++) temp[i] = l[i]; int o[17]= {0}; o[1]=k; o[2]=temp[1]^o[1]; for(int i = 3; i <= m; i++) { o[i] = temp[i-1]^o[i-1]^o[i-2]; } for(int i=1; i<=m; i++) if(yu[o[i]]==((1<<(n+1))-1)) { ui=0; break; } if(ui&&temp[m]==(o[m]^o[m-1])) { int op=0; for(int i=1; i<=m; i++) op+=bcount(yu[o[i]]); if(op<=sum) { sum=op; ko=k; } } if(sum!=1001&&k==((1<<n)-1)) { o[1]=ko; o[2]=temp[1]^o[1]; for(int i = 3; i <= m; i++) { o[i] = temp[i-1]^o[i-1]^o[i-2]; } if(temp[m]==(o[m]^o[m-1])) printf("%d\n",sum); lk=1; } } int main() { int t; scanf("%d",&t); while(t--) { memset(l,0,sizeof(l)); memset(temp,0,sizeof(temp)); memset(yu,0,sizeof(yu)); memset(pk,0,sizeof(pk)); lk=0; ko=0; sum=1001; scanf("%d %d",&m,&n); int h = (1 << n) - 1; for(int k=0; k<=h; k++) yu[k]=((1<<(n+1))-1); for(int k=0; k<=h; k++) { int pp=(k * 2 ^ k^k / 2)&h; if(bcount(yu[pp])>=bcount(k)) yu[pp]=k; } for(int i = 0; i < 17; i++) l[i] = 0; for(int i = 1; i <= m; i++) for (int j = 0; j < n; j++) { scanf("%d",&a); l[i] += (a << j); } for(int k = 0; k < (1 << n); k++) out(k); if(!lk) printf("impossible\n"); } return 0; }