「费解的开关」题解
2021/8/23 23:06:14
本文主要是介绍「费解的开关」题解,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
「费解的开关」题解
原题目链接:Link。
这道题,我们可以先枚举第一行的所有情况,根据第一行的情况来依次确定如何改变。显然:
- 每个灯要么改变要么不改变,即最多改变 \(1\) 次;
- 当第一行被固定后,只会有一种方案使全部灯都亮着;
- 若第 \(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; }
这篇关于「费解的开关」题解的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现
- 2024-05-30我们小公司,哪像华为一样,用得上IPD(集成产品开发)?