P2622 关灯问题 II

问题

P2622 关灯问题 II
现有 $n$ 盏灯，以及 $m$ 个按钮。每个按钮可以同时控制这 $n$ 盏灯，具体影响略，问最少操作几次能把灯全部熄灭。

数据规模：$n \le 10$。

同样的，我们发现这一题的状态非常少，每盏灯只有亮 (1) 和灭 (0) 两种状态，所以总状态数就是 $2^{n}$，考虑状态压缩。

由于这题只询问最少的次数，所以我们可以考虑在状态图上跑 BFS，当然如果问到每一种状态的最少次数，也可以通过添加 dis 数组来保存历史信息。

具体代码略，注意不能修改 cur，若在模拟第一个按钮时修改 cur，第二个按钮就会错误地从第一个按钮的结果继续操作。

这题跟 DP 没什么关系，更本质的理解是状态压缩后，也可以直接在状态空间中跑搜索算法。

本题更关注状态表示，而不是状压 DP。