NOIP 提高 2017 第一轮 第 21 题：如右图所示，共有13个格子。对任何一个格子进行一

题目

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

答案

3

题解

考点定位

本题考「关灯问题」,对应大纲 4.2.4 搜索（难度【5】）。

解题过程

与普及组同题：十字形 13 格取反操作。首行枚举 + 逐行递推 + 末行验证 ⇒ 最少 3 次。

答案：3。

易错提醒

① 枚举首行 2³=8 种方案；② 递推可行性：每行操作唯一由上一行剩余的 1 决定。