C++代码
// 枚举第一行的点击方法,共32种,完成第一行的点击后,固定第一行
// 若某一位(i,j)为0,那就用其所在列的下一行(i+1,j)去执行turn操作,以使(i,j)变为1
// 因此可以从第一行开始递推, 依次确定第二行,第三行直到第五行,如果第五行全为1则代表方案可行
#include <iostream>
#include <cstring>
using namespace std;
const int INF = 1e6;
char g[10][10];
// 中 左 下 右 上
int dx[5] = {0, -1, 0, 1, 0}, dy[5] = {0, 0, 1, 0, -1};
// 把(x,y)以及其上下左右的五个灯全部反转
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){
g[a][b] ^= 1; // '0'和'1'相互转换可以异或1实现, ascii分别为48和49
}
}
}
int work(){
int ans = INF;
char backup[10][10];
// 枚举第一行的点击方法
for(int k = 0; k < 1 << 5; ++k){
int res = 0; // 表示按的次数, 最多不能超过6次
memcpy(backup, g, sizeof(g));
// 根据第一行当前的点击方法k 按下第一行对应的灯
for(int j = 0; j < 5; ++j){
if(k >> j & 1){
res++;
turn(0, j);
}
}
// 固定第一行, 依次递推直到最后一行, 只有当元素为0时才按下其下方的灯
for(int i = 0; i < 4; ++i){
for(int j = 0; j < 5; ++j){
if(g[i][j] == '0'){
res++;
turn(i+1, j);
}
}
}
// 判断最后一行灯的状态是否为全1
bool _success = true;
for(int j = 0; j < 5; ++j){
if(g[4][j] == '0'){
_success = false;
break;
}
}
if(_success) ans = min(ans, res);
// 每个点击方法模拟完毕后要把g恢复成原来的样子
memcpy(g, backup, sizeof(g));
}
if(ans > 6) return -1;
return ans;
}
int main()
{
int n;
cin >> n;
while(n--){
for(int i = 0; i < 5; ++i) cin >> g[i];
cout << work() << endl;
}
return 0;
}