AcWing 95. 费解的开关

题目链接：95. 费解的开关 - AcWing题库

在 01 矩阵的点击游戏中，很容易发现三个性质。

1. 每个位置至多只会被点击一次。
2. 若固定了第一行 (不能再点击第一行)，则满足提议的点击方案至多只有一种。
   其原因是：当第 $i$ 行某一位为 $0$ 是，若前 $i$ 行已经被固定，只能点击第 $i+1$ 行该位置上的数字才能使第 $i$ 行的这一位变成 $0$。从上到下按行使用归纳法可得上述结论。
3. 点击的先后顺序不影响最终结果。

于是，我们不妨先考虑第一行如何点击。

在枚举第一行的点击方法 ($2^5 = 32$ 种) 后，就可以认为第一行 “固定不动”，再考虑第 $2～5$ 行如何点击。

而按照上述性质 $2$，此时第 $2 \sim 5$ 行的点击方案是确定的——从第一行开始递推，当第 $i$ 行某一位为 $0$ 时，点击第 $i + 1$ 行该位置上的数字。

若达到第 $n$ 行是不全为 $0$，说明这种点击方式不合法。

在所有合法的点击方式中取点击次数最少的就是答案。

对第一行的 $32$ 次枚举涵盖了该问题的整个状态空间，因此该做法是正确的。

对于第一样点击方案的枚举，可以采用位运算的方式，枚举 $0 \sim 32$ 这 $32$ 个 $5$ 位二进制数，若二进制数的第 $k (0 \leq k <5)$ 位为 $0$，就点击 $01$ 矩阵第 $1$ 行第 $k + 1$ 列的数字。

完整代码：费解的开关.cpp