刷题：AcWing 95. 费解的开关

时间：2025年6月25日

知识点：递推,位运算

网址：AcWing 95. 费解的开关

来源：《算法竞赛进阶指南》打卡活动

个人感想：一道有一点不好理解，但是理解了后很简单，但又不好实现的递归题。

思路：

• 刚开始写的时候我就猜到了要用递归，但是经历了一番思考，我发现后一行的操作其实是由前一行决定的，后来我看了一下别人的思路，确认了思路没错，为了节省时间，我参考了题解的写法。总的来说，以后应该要求自己完全独立解决。

收获：（有的话就写）

• memcpy(b, a, sizeof(b)); //注意如用sizeof(a)，会造成b的内存地址溢出。
  • 前置头文件: <cstring>
  • 作用1：将s中的字符串复制到字符数组d中
  • 作用2：将指定字符开始复制的位置
    • 例如：
      将s中第14个字符开始的4个连续字符复制到d中。(从0开始)
      memcpy(d, s + 14, 4); // 从s字符串的第15个字符（s[14]）开始，复制到字符串首地址，复制4个字符。
  • 作用3：复制后会覆盖原有部分数据
• op >> i & 1
  • 判断数字op从右往左（←）第i位是不是1，是的话返回1，不是的话返回0。

埋坑：无

完整代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

const int N = 6;
char g[N][N], backup[N][N]; // g表示当前的状态，backup表示备份的状态
int dx[N] = {-1, 0, 1, 0, 0}, dy[N] = {0, 1, 0, -1, 0}; // 左 下 右 上 中


// 这个操作是把(x, y)以及上下左右的灯都变成相反的颜色
void turn(int x, int y)
{
    for(int i = 0; i < 5; i++)
    {
        int a = x + dx[i], b = y + dy[i];
        if(a < 0 || a >= 5 || b < 0 || b >= 5) continue;
        g[a][b] = (g[a][b] == '0') ? '1' : '0';
    }
}

int main()
{
    IOS;
    
    int n;
    cin >> n;
    while(n--)
    {
        for(int i = 0; i < 5; i++)
            cin >> g[i];
        
        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[i][j] == '0')
                    {
                        step ++;
                        turn(i + 1, j); // 如果这个位置是灭的，就按一下下面的灯
                    }
                }
            }

            bool flat = false;
            for(int j = 0; j < 5; j++)
            {
                if(g[4][j] == '0')
                {
                    flat = true;
                    break;
                }
            }

            if(!flat) res = min(res, step);
            memcpy(g, backup, sizeof g);
        }

        if(res > 6) cout << -1 << endl;
        else cout << res << endl;
    }
    
    return 0;
}