---
title: "费解的开关"
created: 2025-11-28
tags:
  - 算法
---

# 费解的开关

## 题目 [费解的开关](https://www.acwing.com/problem/content/97/)

![[image-f9be5d24.png]]

## 思路分析

按一个按钮 会引起上下左右以及它本身5个方式变化

我们从第一行开始按起 发现如果第一行的全按过了 第二行就只能根据第一行的状态来决定按不按

![[image-e538d4c1.png]]

（能影响第一行状态的只有它左右下三个按钮 如果第一行按完了 2位置是关 那么第二行的2位置就一定要按 让第一行2位置变成开 反之第一行按完了
1位置的开 那么第二行的1位置就一定不能按）

有一个特性就是 只需要把第一行的所有位置按与不按的情况枚举出来 根据第一行的每一种状态都会唯一确定一种所有棋盘的状态

（第一行决定第二行 第二行决定第三行 直到最后如果第5行没有全变开 就说明有问题）

要注意的是枚举第一行的意义是：不需要在意第一行的灯是灭是暗，只需把第一行的按法枚举一遍，也就是我们说的 “操作”，每个位置都有两种选择，按(用1表示)或者不按(用0表示)，遍历这32种操作引发的情况，每一次再通过res
= min(res, step);把最小步数存一下，就能找到最优解 （比如10001代表我们选择按第一行编号为0和编号为4的开关，然后对输入数据中第一行这两位执行turn操作）

如何枚举出32种第一行的操作搭配 其实就是二进制枚举子集的问题 或者用dfs也能写

点击按钮的操作就是让自己和上下左右都反转一下开关

![[image-66bfa350.png]]

以左上角为中心 往下是x正方向 往右是y正方向

那么对于一个坐标x,y

它本身就是x+0,y+0 下边就是x+1,y+0 右边x+0,y+1 上x-1,y+0 左x+0,y-1

就可以这样实现按下按钮的翻转操作

```cpp
int dx[5]={0,1,0,-1,0},dy[5]={0,0,1,0,-1};

for(int i=0;i<5;i++){
     int xx=x+dx[i],yy=y+dy[i];
     if(xx>=0 && xx<5 && yy>=0 && yy<5)
     g[xx][yy]^=1;
}
```

可以发现这其实是个不太明显的递推问题

由第一行的状态递推出所有行的状态 但写法与模版有些大相径庭

大部分也是考察在了二进制枚举子集上

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

const int N = 10;

char g[N][N];

void turn(int x,int y)

{

    int dx[5]={0,1,0,-1,0},dy[5]={0,0,1,0,-1};

    for(int i=0;i<5;i++)

    {

        int xx=x+dx[i],yy=y+dy[i];

        if(xx>=0 && xx<5 && yy>=0 && yy<5)

            g[xx][yy]^=1;

    }

}

int work()

{

    int ans = 0x3f3f3f3f;

    //第一行按灯一共有32种可能，对于每一种可能，我们操作选择后，开始固定，

    //此时第一行不一定是全亮的状态，第一行只是32种操作可能的一种

    //这一步是枚举第一行的点击方法，只要第一行固定了，那么满足题意的点击方法就只有一种了。

    //假如第一行是00111

    //k从0到31进行枚举，如果k = 00001，

    //那么代表g矩阵中第一行的第一个灯要点击一下，

    //第一行变为11111

    //k不断变大(0变到31 00001 00010 00011……)

    //假如第一行是00111, k从0到31进行枚举，如果k = 10001，

    //那么代表g矩阵中第一行的第一个灯和最后一个灯要点击一下，

    //第一行变为11100

    //之后固定这一行，后面的行都要根据这个确定的第一行而确定 不断往下做 看是否能全变亮

    //这也就是为什么我们进行备份, 每一次对k的枚举都会改变light。

    for(int k=0;k<(1<<5);k++)

    {

        int res=0;

        char temp[N][N];

        memcpy(temp,g,sizeof g);

        //根据枚举出的对第一行的操作 对第一行某按钮进行点击

        for(int j=0;j<5;j++)

        {

            if(k>>j & 1)

            {

                res++;

                turn(0,j);

            }

        }

        //后面4行都会因为第一行的确定而确定（每行都根据上一行的确定而确定）

        for(int i=0;i<4;i++)

        {

            for(int j=0;j<5;j++)

            {

                if(g[i][j]=='0')

                {

                    res++;

                    turn(i+1,j);

                }

            }

        }

        //只需要看第五行是否全是1即可

        bool flag=true;

        for(int i=0;i<5;i++)

        {

            if(g[4][i]!='1')

            {

                flag=false;

                break;

            }

        }

        if(flag)

            ans = min(ans,res);//更新最少所需步数

        memcpy(g,temp,sizeof g);//还原状态

    }

    if(ans>6)

        return -1;

    else

        return ans;

}

int main()

{

    int n;

    cin>>n;

    while(n--)

    {

        for(int i=0;i<5;i++)

            cin>>g[i];

        cout<< work() <<endl;

    }

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[翻硬币|翻硬币]] 🏠 [[00-刷题理模型]] ➡️ [[递推|递推]]