67 lines
2.8 KiB
C++
67 lines
2.8 KiB
C++
#pragma GCC optimize(2) // 累了就吸点氧吧~
|
||
#include <bits/stdc++.h>
|
||
using namespace std;
|
||
|
||
// 5858 ms
|
||
// 当前状态，当前到最终状态所需步数
|
||
unordered_map<int, int> step;
|
||
|
||
// 改变这个灯及其上下左右相邻的灯的状态
|
||
int turn(int t, int idx) { // idx从0开始
|
||
t ^= (1 << idx); // 改变第idx个灯,0->1,1->0,互换状态，其它灯不动
|
||
if (idx % 5) t ^= (1 << idx - 1); // 不为最左一列,将左侧灯改变
|
||
if (idx >= 5) t ^= (1 << idx - 5); // 不为最上一排,将上侧灯改变
|
||
if (idx < 20) t ^= (1 << idx + 5); // 不为最后一排,将下面灯改变
|
||
if (idx % 5 < 4) t ^= (1 << idx + 1); // 不为最后一列,将右面灯改变
|
||
return t;
|
||
}
|
||
|
||
/* 我们需要知道某个局面是不是出现过，也就是需要把状态记录下来。
|
||
而一个二维的数组状态不好记录，我们喜欢记录一维的。
|
||
每个位置不是0，就是1，最多25个格子，联想到状态压缩，用二进制来表示状态。
|
||
从输入的状态开始，走6步，可以覆盖到哪些数组状态呢？我们可以用状态压缩+Hash表记录下来，最终判断一下
|
||
int x = (1 << 25) - 1;这个状态是不是在Hash表中就行了。
|
||
也可以使用逆向思维：从最终状态逆序遍历，找出可以在6步之内到达最终状态的所有可行状态，应该是一样的
|
||
*/
|
||
void bfs() {
|
||
// 0-2^25-1（25个1），共2^25种状态
|
||
// 最终的状态 全都是 `11111`
|
||
int x = (1 << 25) - 1; // 左移 右移的优先级是最低的，比加减还要低。所以这里的括号是必需的
|
||
queue<int> q;
|
||
q.push(x);
|
||
step[x] = 0; // 记录这个状态是否出现过，如果出现过，是走几步出现的
|
||
|
||
while (q.size()) {
|
||
auto t = q.front();
|
||
q.pop();
|
||
if (step[t] == 6) break; // 反向最多扩展6步
|
||
for (int i = 0; i < 25; i++) {
|
||
x = turn(t, i); // u:当前状态,i:改变i这一位置,x:将此状态改变后的新状态
|
||
if (!step.count(x)) { // 过滤过出现过的状态，只要没有出现过的状态
|
||
step[x] = step[t] + 1;
|
||
q.push(x);
|
||
}
|
||
}
|
||
}
|
||
}
|
||
int main() {
|
||
// 预处理
|
||
bfs();
|
||
|
||
int T;
|
||
scanf("%d", &T);
|
||
while (T--) {
|
||
int g = 0; // g是地图
|
||
for (int i = 0; i < 25; i++) {
|
||
char c;
|
||
// 注意在scanf读取完一个整数，再次读取char时，要清空缓冲区，用" %c"解决
|
||
scanf(" %c", &c);
|
||
g += ((c - '0') << i); // 25个字符二进制压缩成数字
|
||
}
|
||
if (step.count(g) == 0)
|
||
puts("-1");
|
||
else
|
||
cout << step[g] << endl;
|
||
}
|
||
return 0;
|
||
} |