费解的开关-CH0201

《算法竞赛进阶指南》。

基本上可以说又是一个勘误吧。

这本书实在是太不严谨了。代码也不严谨。这可是 github 上面最新的代码呀。这么多年了，一直没有人提出问题吗？

还有，变量和函数的命名实在是草率！连我都不如。

还有，题目都搞错了，人家最后是要全 0 的行列阵，你怎么搞成全 1 的了呢？

还有，字符数组和字符串的用法没有搞清。字符数组如果想要和字符串等价，那么，其最后一个位置一定要留出来，这个是用来放置 '\0' 的。

还有，ans 的初始值搞错了，怎么可能是 7 呢？你多跑几个用例也应该知道，怎么可能一开始给它赋 7 呢？

这道题目难倒是不难，无非是一些位运算模拟遍历的情况，算法的思想也很巧妙，利用递推的思想，直接第一行模拟遍历出来就可以了，然后下面的所有行就都随之确定。最后判断一下这个方案是否满足条件即可。

以下是我理解和纠正过后的代码：

#define _CRT_SECURE_NO_WARNINGS

#include <cstring>
#include <iostream>

using namespace std;

const int N = 6;
int a[N];   // a 中存放的是每次读取到的用户变量
int aa[N];  // aa 是在 recurrence 中使用的临时变量
char s[N];  // 因为后面是把 s 当成字符串来读取输入的，所以，最后一个位置刚好留出来放置 '\0'
int ans;

/**
 * 点击开关
 * x, y 是开关矩阵中的坐标，其中 x 的取值范围是 [1, 5]，y 的取值范围是 [0, 4]
 */
void toggleSwitch(int x, int y) {
    aa[x] ^= (1 << y);
    if (x != 1) aa[x - 1] ^= (1 << y);
    if (x != 5) aa[x + 1] ^= (1 << y);
    if (y != 0) aa[x] ^= (1 << (y - 1));
    if (y != 4) aa[x] ^= (1 << (y + 1));
}

/**
 * 递推
 * p 是当前的第一行的情况
 */
void recurrence(int p) {
    int k = 0;
    // 把 a 赋值给 aa
    memcpy(aa, a, sizeof(a));
    // 模拟第一行的点击
    for (int i = 0; i < 5; i++) {
        if ((p >> i) & 1) {      // 如果 p 的第 i 位是 1，这里其实无论是 0 还是 1 其实都可以，因为是模拟第一行的点击
            toggleSwitch(1, i);  // 把 aa 中的 (1, i) 这个位置的数字变成 1，其原来是 0
            if (++k >= ans) {    // 因为 ans 后续是可能变小的，即在某一种 p 的情况下会变小，不一定一直保持最初的 21
                return;
            }
        }
    }
    // 第一行确定了之后，那么，下面的 4 行就也随之确定了
    for (int x = 1; x < 5; x++) {
        for (int y = 0; y < 5; y++) {
            if ((aa[x] >> y) & 1) {      // 如果 aa[x] 的第 y 位是 1
                toggleSwitch(x + 1, y);  // 点击下一行的位置
                if (++k >= ans) {
                    return;
                }
            }
        }
    }

    if (aa[5] == 0) {  // 如果最后一行是全 0 的话
        ans = k;
    }
}

void solve() {
    // 初始化 a 这个数组
    memset(a, 0, sizeof(a));
    // 依次读入字符串，填入到 s 数组中
    for (int i = 1; i <= 5; i++) {
        cin >> s;  // 这里是把 s 当成一个字符串了
        // 把 s 这个字符串转换成 int 值，然后填入到 a[i] 中去
        for (int j = 0; j < 5; j++) {
            a[i] = a[i] * 2 + (s[j] - '0');
        }
    }
    // 这里 ans 的初始值就设的稍微大一点，因为四行其实最多可以点击 20 次这个开关
    ans = 21;
    // 对第一行的每一种情况进行遍历
    for (int p = 0; p < (1 << 5); p++) {
        recurrence(p);
    }

    if (ans == 21) {  // 所有的情况走下来，都没有找到更小的 ans
        cout << "-1" << endl;
    } else {
        cout << ans << endl;
    }
}

int main() {
    freopen("./liyuds_cases/CH0201.in", "r", stdin);
    int n;
    cin >> n;
    while (n--) {
        solve();
    }
    return 0;
}

以下是原来的代码，仅供留存，

//Author:XuHt
#include <cstring>
#include <iostream>
using namespace std;
const int N = 6;
int a[N], ans, aa[N];
char s[N];

void dj(int x, int y) {
	aa[x] ^= (1 << y);
	if (x != 1) aa[x-1] ^= (1 << y);
	if (x != 5) aa[x+1] ^= (1 << y);
	if (y != 0) aa[x] ^= (1 << (y - 1));
	if (y != 4) aa[x] ^= (1 << (y + 1));
}

void pd(int p) {
	int k = 0;
	memcpy(aa, a, sizeof(a));
	for (int i = 0; i < 5; i++)
		if (!((p >> i) & 1)) {
			dj(1, i);
			if (++k >= ans) return;
		}
	for (int x = 1; x < 5; x++)
		for (int y = 0; y < 5; y++)
			if (!((aa[x] >> y) & 1)) {
				dj(x + 1, y);
				if (++k >= ans) return;
			}
	if (aa[5] == 31) ans = k;
}

void abc() {
	memset(a, 0, sizeof(a));
	for (int i = 1; i <= 5; i++) {
		cin >> (s + 1);
		for (int j = 1; j <= 5; j++) a[i] = a[i] * 2 + (s[j] - '0');
	}
	ans = 7;
	for (int p = 0; p < (1 << 5); p++) pd(p);
	if (ans == 7) cout << "-1" << endl;
	else cout << ans << endl;
}

int main() {
	int n;
	cin >> n;
	while (n--) abc();
	return 0;
}

按：不知这个 XuHt 是何方人士，代码还是要写写严谨啦。