依题意，题目给我们一个5X5的灯泡，改变一个灯泡的开关伴随的是上下左右的灯泡也会改变亮暗状态。我们可以通过枚举决定是否按第一层的各个开关，由于变换的范围是上下左右，若此时第一层某个位置的灯泡还是灭着的，那第二层的相同位置就必须要按一次开关，相反若灯泡是亮着的就不能再按一次。以此类推即只要第一行的初始状态确定，则接下来的层按不按开关的状态就已经确定了。最后只要判断当前是否为全亮的状态便可以判断方案的有效性。
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int N = 6; char g[N][N], backup[N][N]; void turn(int x, int y) //模拟按一次开关 { int dx[5] = { -1,0,1,0,0 }; int dy[5] = { 0,1,0,-1,0 }; for (int i = 0; i < 5; i++) { int ax = x + dx[i]; int ay = y + dy[i]; if (ax >= 5 || ax < 0 || ay >= 5 || ay < 0) continue; g[ax][ay] ^= 1; } } int main() { int n; scanf("%d", &n); while (n--) { for (int i = 0; i < 5; i++) cin >> g[i]; //以字符串的形式读入 int ans = 10; for (int i = 0; i < 32; i++) //通过 位 来枚举 { memcpy(backup, g, sizeof(g)); //设置备份 int count = 0; for (int j = 0; j < 5; j++) { if (i >> j & 1) //确定每位为1则按一次开关 { count++; turn(0, j); } } for (int j = 0; j < 4; j++) //类推模拟下面几层 { for (int z = 0; z < 5; z++) { if (g[j][z] == '0') { count++; turn(j + 1, z); } } } bool sign = false; for (int j = 0; j < 5; j++) //检测最后结果 { if (g[4][j] == '0') { sign = true; break; } } if (!sign) { ans = min(ans, count); } memcpy(g, backup, sizeof(g)); //回归备份 } if (ans > 6) { ans = -1; } printf("%d\n", ans); } return 0; }
