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

题面

传送门[https://www.acwing.com/problem/content/description/97/]

分析

考虑逐行分析，以行递推
如果不再改变第一行，则满足题意的点击方案最多1种
理由是：如果第i行某一位为0，由于第i行固定，只能点击第i+1行这个位置才能将其改变为1，归纳可得
所以直接开始遍历
在固定第一行之前先对第一行进行修改（不能直接贪心不修改第一行）
修改的意义在于找出第一行有被点击的最优解
第一行5个元素的修改方案可以用五位二进制数表示
例如10110，其中1表示修改，0表示不修改，则0~31可表示第一行元素的修改方案

代码

#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("%d\n",ANS);
	ANS = 7;//初始化大于6就行
}

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