刷题：AcWing 95. 费解的开关
题目名称：AcWing 95. 费解的开关时间：2025年6月25日
知识点：递推,位运算
网址：AcWing 95. 费解的开关
来源：《算法竞赛进阶指南》打卡活动
个人感想：一道有一点不好理解，但是理解了后很简单，但又不好实现的递归题。
思路：
[*]刚开始写的时候我就猜到了要用递归，但是经历了一番思考，我发现后一行的操作其实是由前一行决定的，后来我看了一下别人的思路，确认了思路没错，为了节省时间，我参考了题解的写法。总的来说，以后应该要求自己完全独立解决。
收获：（有的话就写）
[*]memcpy(b, a, sizeof(b)); //注意如用sizeof(a)，会造成b的内存地址溢出。
[*]前置头文件:
[*]作用1：将s中的字符串复制到字符数组d中
[*]作用2：将指定字符开始复制的位置
[*]例如：
将s中第14个字符开始的4个连续字符复制到d中。(从0开始)
memcpy(d, s + 14, 4); // 从s字符串的第15个字符（s）开始，复制到字符串首地址，复制4个字符。
[*]作用3：复制后会覆盖原有部分数据
[*]op >> i & 1
[*]判断数字op从右往左（←）第i位是不是1，是的话返回1，不是的话返回0。
埋坑：无
完整代码：
#include#include#include#includeusing namespace std;#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)const int N = 6;char g, backup; // g表示当前的状态，backup表示备份的状态int dx = {-1, 0, 1, 0, 0}, dy = {0, 1, 0, -1, 0}; // 左 下 右 上 中// 这个操作是把(x, y)以及上下左右的灯都变成相反的颜色void turn(int x, int y){ for(int i = 0; i < 5; i++) { int a = x + dx, b = y + dy; if(a < 0 || a >= 5 || b < 0 || b >= 5) continue; g = (g == '0') ? '1' : '0'; }}int main(){ IOS; int n; cin >> n; while(n--) { for(int i = 0; i < 5; i++) cin >> g; int res = 10; for(int op = 0; op < 32; op++) { memcpy(backup, g, sizeof g); // 先将备份的数组赋值给g int step = 0; for(int i = 0; i < 5; i++) { if(op >> i & 1) { step ++; turn(0, i); } } for(int i = 0; i < 4; i++) { for(int j = 0; j < 5; j++) { if(g == '0') { step ++; turn(i + 1, j); // 如果这个位置是灭的，就按一下下面的灯 } } } bool flat = false; for(int j = 0; j < 5; j++) { if(g == '0') { flat = true; break; } } if(!flat) res = min(res, step); memcpy(g, backup, sizeof g); } if(res > 6) cout
页:
[1]