YetAnotherBoardGame

作者：聂恺辰

关键词：搜索

题目简述

给一个$N*M$的黑白棋盘，你的目标是把它们都变成黑色，每次可以对一个点进行两种操作。

1.以他为中心的十字型区域颜色全部取反

2.以他为中心的十字型区域除了自己颜色全部取反

并且每行每列都不能进行不同的操作，问最少进行多少操作完成，如果不能返回-1

数据范围

$N,M<=13$

算法

首先显然每个点至多进行一次操作

考虑暴力做法，即枚举第一行进行什么操作及对哪些点进行操作，然后依次做下面的行。

由于上一行的状态只能由这一行来改变，所以这一行要更改的点有且仅有上一行为白色的列对应的点，然后根据限制之前的来决定这一层要用哪种操作或者是两种都可以或是不能操作，然后递归搜索

事实上这种算法的时间复杂度是$O(3^M)$的,能过

时间复杂度证明

这个复杂度等于$\sum\limits_{i=0}^{M}C_{M}^{i}*2^{M-i}$ 考虑枚举的列有i列，这样的情况有$C_{M}^{i}$种，还剩M-i列，枚举剩余的M-i列的复杂度是$O(2^{M-i})$的

为什么在枚举的列确定的情况下搜索的复杂度是$O(2^{M-i})$的呢，因为每一列都一定会在固定的某行被确定是哪种操作，所以没有重复的搜索，复杂度是$O(2^{M-i})$的

而我们发现这个式子与枚举一个集合的所有子集的所有子集的复杂度的式子是一样的

，并且我们知道枚举一个集合的所有子集的所有子集的复杂度是$O(3^M)$的

具体来讲，每一列会有三种情况，分别是由枚举确定，在后边的搜索中确定为操作1和在后边的搜索中确定为操作2，所以复杂度是$O(3^M)$的，这是可以过的