• 欢迎光临~

# 费解的开关[二进制、递推]

## 代码

``````#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
inline int read() {
register int x = 0, f = 1;
register char c = getchar();
while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0',c = getchar();
return x * f;
}
int n,ANS = 10;
const int MAXN = 6;
int mat[MAXN][MAXN],backup[MAXN][MAXN];//mat储存矩阵，backup备份初始矩阵
int movex[5] = {0, -1, 0, 1, 0},movey[5] = {0, 0, -1, 0, 1};//每一对组合分别表示不动、左、下、右、上

void change(int x,int y) {//修改五个位置的值
for (int i(0); i <= 4; i++){
int mox = x + movex[i],moy = y + movey[i];
if (mox < 1 || mox > 5 || moy < 1 || moy > 5) continue;//越过矩阵范围直接跳
mat[mox][moy] ^= 1;
}
}

void init(){
getchar();//读掉回车
for (int i(1); i <= 5; i++){
for (int j(1); j <= 5; j++){
mat[i][j] = (getchar() - '0');
}
getchar();//结尾也要读掉回车
}
}

void doit() {
for (int i(0); i < 1 << 5; i++) {//枚举第一行修改方案
int ans = 0;
memcpy(backup, mat, sizeof(mat));
for (int j(0); j <= 4; j++)
if (i >> j & 1) {//位运算操作取出i中1的位置
ans++;
change(1, j + 1);
}
for (int j(1); j <= 4; j++)
for (int k(1); k <= 5; k++)
if (!mat[j][k]) {//暴力修改
ans++;
change(j + 1,k);
}
bool check = true;
for (int j(1); j <= 5; j++)
if (!mat[5][j]){//遍历最后一行是否全为1
check = false;
break;
}
if (check) ANS = min (ANS, ans);
memcpy(mat, backup, sizeof(backup));
}
if (ANS > 6) puts("-1");
else printf("%dn",ANS);
ANS = 7;//初始化大于6就行
}

int main() {
cin >> n;
while (n--){
init();
doit();
}
return 0;
}

``````