思路:首先确定第一行的操作,每一行都是由下一行的操作影响,最后一行全为1,则答案合法。
通过枚举第一行 32 种情况,对第一行每一个位置的每一种情况进行判断,递推每一种情况的结果,找出最小答案。(这种操作可能会减小递推结果,也可能增加)
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 6;
char g[N][N], backup[N][N];
int dx[5] = {-1, 0, 1, 0, 0}, dy[5] = {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 >= 5 && a < 0 && b >= 5 && b < 0)continue;
g[a][b] ^= 1;
}
}
int work(){
int ans = 10000;
for(int i = 0; i < 1 << 5; i ++){
int res = 0;
memcpy(backup, g , sizeof g);
for(int j = 0; j < 5; j ++){
if(i >> j & 1){
res ++;
turn(0, j);
}
}
for (int i = 0; i < 4; i ++ ){
for (int j = 0; j < 5; j ++ ){
if(g[i][j] == '0'){
res ++;
turn(i + 1, j);
}
}
}
bool dark = true;
for(int j = 0; j < 5; j ++){
if(g[4][j] == '0'){
dark = false;
break;
}
}
if(dark)ans = min(ans, res);
memcpy(g, backup, sizeof backup);
}
if(ans > 6)return -1;
return ans;
}
int main()
{
int T;
cin >> T;
while(T --){
for(int i = 0; i < 5; i ++)
cin >> g[i];
cout << work() << endl;
}
}