从上往下枚举,能影响i - 1,j点的只有i, j点,所以i,j点受到i - 1, j点的限制,
(i - 1点为0,则i, j必须按,i - 1, j为0,则i, j不能按)
对于第一行暴力枚举,最后判断一下最后一行是否全亮即可
#include <bits/stdc++.h>
using namespace std;
const int N = 6;
char s[N][N];
char a[N][N];
int xx[] = {0, 0, 1, -1, 0};
int yy[] = {1, -1, 0, 0, 0};
int main()
{
int T;
cin >> T;
while(T -- )
{
for(int i = 0; i < 5; i ++ )
cin >> s[i];
int cnt = 7;
for(int op = 0; op < 1 << 5; op ++ )
{
int t = 0;
memcpy(a, s, sizeof s);
for(int i = 0; i < 5; i ++ )
if(op >> i & 1)
{
t ++ ;
for(int k = 0; k < 5; k ++ )
{
int ax = 0 + xx[k];
int ay = i + yy[k];
if(ax < 0 || ax >= 5 || ay < 0 || ay >= 5) continue;
a[ax][ay] ^= 1;
}
}
for(int i = 1; i < 5; i ++ )
for(int j = 0; j < 5; j ++ )
if(a[i - 1][j] == '0')
{
t ++ ;
for(int k = 0; k < 5; k ++ )
{
int ax = i + xx[k];
int ay = j + yy[k];
if(ax < 0 || ax >= 5 || ay < 0 || ay >= 5) continue;
a[ax][ay] ^= 1;
}
}
for(int i = 0; i < 5; i ++ ) if(a[4][i] == '0') t = 7;
cnt = min(cnt, t);
}
if(cnt <= 6) cout << cnt << endl;
else cout << -1 << endl;
}
}