这题还挺有意思的,碰见过两次了。我的想法主要是把这个矩阵存储为一个int类型的数matrix里(毕竟只有25位,够了)。
然后我这题还做了挺久的,主要是因为有两个bug。最坑爹的bug在于我忘记了每次都将matrix设置为原本的值(枯了。
另外就是我的代码是对书上的思路的实现。
#include<iostream>
#include <string.h>
#include <algorithm>
#include<fstream>
#include<vector>
using namespace std;
int n;
int matrix = 0;
int temp_matrix = 0;
void click(int index) {
matrix ^= 1 << index;
int l = (index / (int)5) * (int)5;
int r = l + 4;
if (index - 1 >= l)matrix ^= 1 << (index - 1);
if (index + 1 <= r)matrix ^= 1 << (index + 1);
if (index + 5 <= 24)matrix ^= 1 << (index + 5);
if (index - 5 >= 0)matrix ^= 1 << (index - 5);
}
int main() {
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
cin >> n;
char temp;
for (int i = 0; i < n; ++i) {
matrix = 0;
temp_matrix = 0;
int min_c = 7;
for (int j = 24; j >= 0; --j) { //输入矩阵并将其转化为int类型的数
cin >> temp;
if (temp == '1') {
temp_matrix |= 1 << j;
}
}
for (int k = 0; k < 1 << 5; ++k) { //对于32种情况进行一一枚举
matrix = temp_matrix;
int num = 0;
for (int t = 0; t < 5; ++t) { //首先对第一行进行操作
if ((k >> t) & 1) {
click(24 - t);
++num;
}
}
for (int a = 19; a >= 0; --a) { //然后是从第二行到最后一行
if (!((matrix >> (a + 5)) & 1)) {
click(a);
++num;
}
if (matrix == (1 << 25) - 1) {
min_c = min(min_c, num);
}
if (num > 6) {
break;
}
}
}
if (min_c == 7)cout << -1 << endl;
else cout << min_c << endl;
}
return 0;
}