P10449 费解的开关

题目大意

每次拉灯会影响上下左右和自己 5 个灯的状态，给定初始状态，要求判断是否能在 $6$ 步以内打开所有灯。

题目分析

首先我们发现，一个灯被操作偶数次后状态不变，奇数次后状态改变。这启示我们，一个灯的状态和它被操作的顺序无关，我们可以任意调整开关灯操作的顺序。

既然如此我们逐行进行更改。

1. 考虑第一行，因为灯最多只会受到它自身和左、右、下三个灯的影响，也就是说，如果这一行的灯无法在行内解决，我们还可以通过操作它下面的灯来补救。

2. 考虑后面每一行，若上一行这个位置的的灯是开着的，那么必须操作这个灯，来让他上一行的灯关上。也就是说，只要确定第一行的状态，就可以顺势推出其他所有行的状态。

3. 因为本题数据规模较小，且我们并不知道如何操作第一行是最优的。考虑枚举第一行的操作状态。

Code

实现时注意每次枚举后都要还原状态。

优化：可加上最优性剪枝，但本题数据范围较少，不加也能过。