「费解的开关」题解

原题目链接：Link。

这道题，我们可以先枚举第一行的所有情况，根据第一行的情况来依次确定如何改变。显然：

1. 每个灯要么改变要么不改变，即最多改变 \(1\) 次；
2. 当第一行被固定后，只会有一种方案使全部灯都亮着；
3. 若第 \(i\) 行已经被固定，且第 \(j\) 个灯灭着，我们就必须按处于 \((i + 1, j)\) 的灯（下一行的灯）。

代码如下：

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 10;

int n, ans;
bool a[MAXN][MAXN], b[MAXN][MAXN];
string s;

bool check(int x, int y) {return x >= 0 && y >= 0;}

void mov(int x, int y) {
	if (check(x, y)) a[x][y] ^= 1;
	if (check(x - 1, y)) a[x - 1][y] ^= 1;
	if (check(x + 1, y)) a[x + 1][y] ^= 1;
	if (check(x, y - 1)) a[x][y - 1] ^= 1;
	if (check(x, y + 1)) a[x][y + 1] ^= 1; // 模拟开灯，为了防止越界引入 check 函数
}
int main() {
	scanf("%d", &n);
	while (n--) {
		getline(cin, s); ans = 0x7ffffff;
		for (int i = 0; i < 5; i++) {
			cin >> s;
			for (int j = 0; j < 5; j++)
				b[i][j] = a[i][j] = s[j] == '1'; // 因为要在 a 数组上操作，所以用一个 b 数组记录初始数组
		}
		for (int now = 0; now < 1 << 5; now++) { // 二进制枚举第一行的所有情况
			memcpy(a, b, sizeof(b)); // 操作完 a 数组，把原来的复制过来
			int tot = 0, t;
			for (int bit = 0; bit < 5; bit++) {
				int t = now >> bit & 1; // now 的第 bit 位
				if (a[0][bit] != t) {
					mov(0, bit);
					tot++;
				}
			} // 按 now 改变 a 数组的第一行，同时记录操作次数，不同就 tot++
			for (int i = 1; i < 5; i++)
				for (int j = 0; j < 5; j++) {
					if (!a[i - 1][j]) { // 如果这个位置的上一行的灯灭了
						mov(i, j); // 按这个位置，同时 tot++
						tot++;
					}
				}
			bool flag = true;
			for (int i = 0; i < 5; i++)
				if (!a[4][i]) {flag = false; break;} // 最后扫一遍数组，看是不是全部开着
			if (flag) ans = min(ans, tot); // 是就记录答案
		}
		if (ans <= 6) printf("%d\n", ans);
		else puts("-1"); // 这里不能直接输出，还要判断是否 <= 6
	}
    return 0;
}