Loading... [来自KeChang](https://blog.silvery.me/) ### 题目描述 你玩过“拉灯”游戏吗？ 25盏灯排成一个5×5的方形。每一个灯都有一个开关，游戏者可以改变它的状态。 每一步，游戏者可以改变某一个灯的状态。 游戏者改变一个灯的状态会产生连锁反应：和这个灯上下左右相邻的灯也要相应地改变其状态。 我们用数字1表示一盏开着的灯，用数字0表示关着的灯。 下面这种状态 ``` 10111 01101 10111 10000 11011 ``` 在改变了最左上角的灯的状态后将变成： ``` 01111 11101 10111 10000 11011 ``` 再改变它正中间的灯后状态将变成： ``` 01111 11001 11001 10100 11011 ``` 给定一些游戏的初始状态，编写程序判断游戏者是否可能在6步以内使所有的灯都变亮。 ### 输入格式 第一行输入正整数n，代表数据中共有n个待解决的游戏初始状态。 以下若干行数据分为n组，每组数据有5行，每行5个字符。 每组数据描述了一个游戏的初始状态。 各组数据间用一个空行分隔。 ### 输出格式 一共输出n行数据，每行有一个小于等于6的整数，它表示对于输入数据中对应的游戏状态最少需要几步才能使所有灯变亮。 对于某一个游戏初始状态，若6步以内无法使所有灯变亮，则输出−1。 ### 数据范围 0<n≤500 ### 输入样例： ``` 3 00111 01011 10001 11010 11100 11101 11101 11110 11111 11111 01111 11111 11111 11111 11111 ``` ### 输出样例： ``` 3 2 -1 ``` ### 题目分析 #### BFS 暴力 正推 TLE 首先，我们定义一个结构体 `coordinate` 来存储灯的坐标。然后，我们定义一个数组 `dir` 来存储上下左右四个方向。 接下来，我们定义一个函数 `change` 来改变灯的状态。这个函数接受两个参数：一个是当前灯的状态 `g`，另一个是要改变的灯的位置 `k`。在这个函数中，我们首先改变位置为 `k` 的灯的状态，然后遍历它上下左右相邻的灯，改变它们的状态。 然后，我们定义一个函数 `solve` 来解决这道题。在这个函数中，我们首先读入数据，并初始化一些变量。然后，我们使用 BFS 算法来搜索答案。在每一步中，我们遍历队列中的所有元素，并对每一个元素进行扩展。扩展时，我们枚举所有可能改变状态的灯，并调用 `change` 函数来改变它们的状态。如果改变后所有灯都亮了，则输出答案并返回；否则，将新状态加入队列中。 最后，在主函数中，我们读入数据组数 `n`，并调用 `solve` 函数来解决每一组数据。 ``` #include <iostream> #include <queue> #include <bitset> #include <unordered_map> using namespace std; const int N = 25; int n; char c; typedef struct { int i, j; }coordinate; coordinate dir[4] = {{1,0},{0,1},{-1,0},{0,-1}}; inline bitset <N> change(bitset <N> g, int k) { g[k] = !g[k]; int i = k / 5, j = k % 5; for (int l = 0; l < 4; ++l) { int I = i + dir[l].i, J = j + dir[l].j; if (I >= 0 && I < 5 && J >= 0 && J < 5) { int t = I * 5 + J; g[t] = !g[t]; } } return g; } void solve() { int cnt = 0; bool u = false; bitset <N> g; queue <bitset <N>> que[2]; unordered_map <bitset <N>,bool> mp; for (int i = 0; i < N; ++i) { cin >> c; if (c - '0') g[i] = 1; else g[i] = 0; } if (g.count() == N) { cout << "0\n"; return ; } que[u].push(g); while(1) { ++cnt; if (cnt > 6) { cout << "-1\n"; break; } while(que[u].size()) { auto t = que[u].front(); que[u].pop(); for (int i = 0; i < N; ++i) { auto buf = change(t,i); if (buf.count() == N) { cout << cnt << '\n'; return ; } if (!mp[buf]) { mp[buf] = 1; que[!u].push(buf); } } } u = !u; } } int main () { ios::sync_with_stdio(0); cin.tie(0); cin >> n; while(n--) solve(); return 0; } ``` #### BFS 打表 逆推 TLE 首先，我们定义一个结构体 `coordinate` 来存储灯的坐标。然后，我们定义一个数组 `dir` 来存储上下左右四个方向。 接下来，我们定义一个函数 `change` 来改变灯的状态。这个函数接受两个参数：一个是当前灯的状态 `g`，另一个是要改变的灯的位置 `k`。在这个函数中，我们首先改变位置为 `k` 的灯的状态，然后遍历它上下左右相邻的灯，改变它们的状态。 然后，我们定义一个函数 `eval` 来预处理所有可能的答案。在这个函数中，我们使用 BFS 算法来搜索答案。在每一步中，我们遍历队列中的所有元素，并对每一个元素进行扩展。扩展时，我们枚举所有可能改变状态的灯，并调用 `change` 函数来改变它们的状态。如果改变后所有灯都亮了，则将答案存入哈希表中；否则，将新状态加入队列中。 最后，在主函数中，我们首先调用 `eval` 函数来预处理所有可能的答案。然后，读入数据组数 `n`，并对于每一组数据，读入初始状态并在哈希表中查找答案。 ``` #include <iostream> #include <bitset> #include <queue> #include <unordered_map> using namespace std; const int N = 25; typedef struct { int i, j; }coordinate; coordinate dir[4] = {{1,0},{0,1},{-1,0},{0,-1}}; unordered_map <bitset <N>, int> ans; inline bitset <N> change(bitset <N> g, int k) { g[k] = !g[k]; int i = k / 5, j = k % 5; for (int l = 0; l < 4; ++l) { int I = i + dir[l].i, J = j + dir[l].j; if (I >= 0 && I < 5 && J >= 0 && J < 5) { int t = I * 5 + J; g[t] = !g[t]; } } return g; } void eval() { int cnt = 0; bool u = 0; bitset <N> bt; queue <bitset <N>> que[2]; unordered_map <bitset <N>, bool> mp; for (int i = 0; i < N; ++i) bt[i] = 1; ans[bt] = 0; que[u].push(bt); while(cnt <= 6) { ++cnt; while(que[u].size()) { auto t = que[u].front(); que[u].pop(); for (int i = 0; i < N; ++i) { auto buf = change(t,i); if (!mp[buf]) { mp[buf] = 1; ans[buf] = cnt; que[!u].push(buf); } } } u = !u; } } int n; char c; int main () { ios::sync_with_stdio(0); cin.tie(0); eval(); cin >> n; while(n--) { bitset <N> bt; for (int i = 0; i < N; ++i) { cin >> c; bt[i] = (c - '0'); } ans.find(bt) == ans.end() ? cout << "-1\n" : cout << ans[bt] << '\n'; } return 0; } ``` #### 递推 首先，我们定义一个结构体 `coordinate` 来存储灯的坐标。然后，我们定义一个数组 `dir` 来存储上下左右四个方向。 接下来，我们定义一个函数 `on` 来改变灯的状态。这个函数接受三个参数：一个是要改变的灯的位置 `p`，一个是当前灯的状态 `g`，另一个是步数计数器 `cnt`。在这个函数中，我们首先将步数计数器加一，然后遍历位置为 `p` 的灯上下左右相邻的灯，改变它们的状态。 然后，我们定义一个函数 `solve` 来解决这道题。在这个函数中，我们首先读入数据，并初始化一些变量。然后，我们枚举第一行所有可能的状态，并模拟游戏过程。在模拟过程中，我们从上往下遍历每一行，并对每一行进行处理。如果当前行某个位置的灯是关着的，则将下一行对应位置的灯打开。最后，如果所有灯都亮了，则更新答案。 最后，在主函数中，我们读入数据组数 `n`，并调用 `solve` 函数来解决每一组数据。 ``` #include <iostream> #include <bitset> using namespace std; const int N = 5, M = 25; typedef struct { int i, j; }coordinate; coordinate dir[N] = {{1,0},{0,1},{0,0},{-1,0},{0,-1}}; int n; void on(int p, bitset <M>& g, int* cnt) { ++(*cnt); int i = p / N, j = p % N; for (int k = 0; k < N; ++k) { int I = i + dir[k].i, J = j + dir[k].j, u = I * N + J; if (I >= 0 && I < N && J >= 0 && J < N) g[u] = !g[u]; } } void solve() { int res = 0x3f3f3f3f; char c; bitset <M> bt, buf; for (int i = 0; i < M; ++i) { cin >> c; bt[i] = (c - '0'); } buf = bt; for (int i = 0; i < (1 << 6); ++i) { bt = buf; int t = i, p = 0, cnt = 0; while(t) { if (t & 1) on(p, bt, &cnt); ++p; t >>= 1; } for (int i = 0; i < M - N; ++i) { if (!bt[i]) on(i + N,bt, &cnt); } if (bt.count() == M) res = min(res, cnt); } if (res > 6) res = -1; cout << res << '\n'; } int main () { ios::sync_with_stdio(0); cin.tie(0); cin >> n; while(n--) solve(); return 0; } ``` 最后修改：2023 年 08 月 06 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏