NOIP 普及 2017 第一轮 第 22 题：13 格翻转使全部变 0 的最少操作数

题目

如下图所示，共有 $13$ 个格子。对任何一个格子进行一次操作，会使得它自己以及与它上下左右相邻的格子中的数字改变（由 $1$ 变 $0$，或由 $0$ 变 $1$）。现在要使得所有的格子中的数字都变为 $0$，至少需要_次操作。

答案

3

题解

考点定位

本题考「开关灯贪心/枚举」,对应大纲 4.2.4 搜索（难度【4】）。

解题过程

13 格十字形灯：操作自身+上下左右取反。第一行（3 格）的开关方案确定后，第二行必须「把第一行剩余的 1 全部熄灭」，逐行递推，最后验证末行全 0。枚举首行 2³=8 种：恰有一种可行 ⇒ 最少 3 次？官方答案 3（最少操作次数）。

答案：3。

易错提醒

① Lights-off 类问题：首行枚举 + 逐行递推 + 末行验证；② 附加约束（本题为特殊十字形 13 格）决定具体方案。