AcWing
95. 费解的开关
每一个位置顶多只会操作一次。因为如果操作两次的话，相当于不操作，必然不满足最优解。
在一套方案中，操作的顺序无关紧要。
如果确定了第i行的操作方案，那么第i+1行的操作方案唯一确定。因为如果第i行选中了某一操作方案，对于第i行的某种状态，那么只有第i+1行才能改变第i行的状态，使其全亮了。
所以，可以枚举第1行的操作方案，一共$2^5$种，每一种方案，对应第1行的一种状态。那么接下来，第2行确定了唯一的方案，使得第1行的状态修改为全亮；第3行确定了唯一的方案，使得第2行的状态修改为全亮；……；最终，最后一行确定了唯一的方案，使得倒数第二行的状态修改为全亮。再检查最后一行是否为全亮，否则整个方案就是不合法的，接着枚举第一行方案的下一种情况。
枚举第1行的操作方案，可以使用二进制的方式，00000 ~ 11111，表示第一行的操作情况，即从0循环到31.
小技巧：'0' ^ 1 == '1'；'1' ^ 1 == '0'.
#include <bits/stdc++.h>
using namespace std;
int t;
char g[6][6], backup[6][6];
int dx[5] = {1, -1, 0, 0, 0};
int dy[5] = {0, 0, 0, 1, -1};
void turn(int x, int y){
for(int i = 0; i <= 4; i++){
if(x + dx[i] < 0 || x + dx[i] > 4 || y + dy[i] < 0 || y + dy[i] > 4) continue;
else g[x + dx[i]][y + dy[i]] ^= 1; // ('0' <==> '1') with '^'
}
}
int main(){
cin >> t;
while(t--){
for(int i = 0; i <= 4; i++) cin >> backup[i];
int res = 10;
for(int op = 0; op <= 31; op++){ // 00000 ~ 11111，表示第一行的操作情况
int step = 0;
memcpy(g, backup, sizeof backup);
for(int i = 0; i <= 4; i++){
if(op >> i & 1){
turn(0, i);
step++;
}
}
for(int i = 1; i <= 4; i++){
for(int j = 0; j <= 4; j++){
if(g[i - 1][j] == '0'){
turn(i, j);
step++;
}
}
}
bool dark = false;
for(int j = 0; j <= 4; j++) if(g[4][j] == '0'){
dark = true;
break;
}
if(!dark) res = min(res, step);
}
if(res > 6) res = -1;
cout << res << endl;
}
return 0;
}