格子连动问题【NOIP2017初赛 】

2021年8月14日 | 分类: 【编程】

【题目】

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

【解析】

尽可能操作一次多改变几个格子。

注意:对任何一个格子进行一次操作,会使得它自己以及与它上下左右相邻的格子中的数字改变(由1变0,或由0变1)

初始状态:

  1
 001
01001
 011
  0

第1步:第三行第四个;因为此时这个格子0周围的1最多为3。

第1步之后状态:

  1
 000
01110
 010
  0

第2步:第三行第三个;因为此时这个格子1周围的1最多为3。

第2步之后状态:

  1
 010
00000
 000
  0

第3步:第一行第一个;因为此时这个格子1周围的1最多为1。

第3步之后状态:

  0
 000
00000
 000
  0

现在要使得所有的格子中的数字都变为0,至少需要(3)次操作。