思路:每一个位置都有两种选择,按或者不按,那么我们先枚举第一行的所有方案 $(00000)_2$ ~ $(11111)_2$,其中方案用二进制表示,0 代表这个位置不按,1 代表按。
枚举之后,第一行的状态已经确定,后续我们就可以根据第一行的状态确定 2 ~ 5 行的相应状态。以样例第一个数据为例,假设当前枚举第一行的方案是 $(00000)_2$,就是第一行所有位置都不按,第一行仍然是 00111,从左到右枚举第一行,遇到 ‘0’ 我们就把第二行同一列的相应位置翻转一下同时更新操作次数,这样之后第一行就全部变成了 1;然后从左到右枚举第二行,执行同样的操作······当第四行枚举完了以后,前面四行都变成了 1,我们只需要判断最后一行是否全为 1 即可,如果是,那么就说明这个方案是合法的。如果全部操作次数的最小值大于 6,那么说明无解;否则输出答案即可。
代码:
#pragma GCC optimize(3)
#include <iostream>
#include <cstring>
using namespace std;
const int N = 6, INF = 0x3f3f3f3f;
int n;
char g[N][N], tp[N][N];
int dx[] = {-1, 0, 1, 0, 0};
int dy[] = {0, 1, 0, -1, 0};
void turn(int x, int y)
{
for(int i = 0; i < 5; i++)
{
int a = x + dx[i], b = y + dy[i];
if(a < 0 || a >= 5 || b < 0 || b >= 5) continue;
tp[a][b] = (tp[a][b] == '1' ? '0' : '1');
}
}
int main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n;
while(n--)
{
for(int i = 0; i < 5; i++) cin >> g[i];
int res = INF;
for(int op = 0; op < 32; op++)
{
int cnt = 0;
memcpy(tp, g, sizeof g);
//op the first line
for(int i = 0; i < 5; i++)
if(op >> i & 1)
turn(0, i), cnt++;
//op the 2nd ~ 5th line
for(int i = 0; i < 4; i++)
{
for(int j = 0; j < 5; j++)
{
if(tp[i][j] == '0')
turn(i + 1, j), cnt++;
}
}
//legal?
bool flag = true;
for(int i = 0; i < 5; i++)
if(tp[4][i] == '0')
flag = false;
//update the minimum
if(flag && res > cnt) res = cnt;
}
cout << (res > 6 ? -1 : res) << endl;
}
return 0;
}