..
AcWing 95. 费解的开关
题目链接:95. 费解的开关 - AcWing题库
在 01 矩阵的点击游戏中,很容易发现三个性质。
- 每个位置至多只会被点击一次。
- 若固定了第一行 (不能再点击第一行),则满足提议的点击方案至多只有一种。
其原因是:当第 $i$ 行某一位为 $0$ 是,若前 $i$ 行已经被固定,只能点击第 $i+1$ 行该位置上的数字才能使第 $i$ 行的这一位变成 $0$。从上到下按行使用归纳法可得上述结论。 - 点击的先后顺序不影响最终结果。
于是,我们不妨先考虑第一行如何点击。
在枚举第一行的点击方法 ($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