SSOJ3015C十六夜咲夜
3733+
作者：crxis 发布：2019-04-28 分类：深度优先搜索
题目大意：一个n行m列的矩阵，#表示垃圾，一次可以将连续r行或c列的垃圾清掉，至少需要清理多少次？
题目描述
红魔馆又要开始大清扫了。按理说在她的管理下，也没有什么容易弄脏的地方。然而，房间内却有几座雕像是需要仔细进行打扫的。
于是，咲夜召集了一批妖精女仆。每个妖精女仆可以清理连续的 R 行，或是连续的 C 列。她想知道，最少需要多少妖精女仆可以打扫整个房间的所有雕像。
输入
第一行，包含四个整数 N, M, R, C，分别表示房间的行列数，和可以连续清扫的行列数。
接下来 N 行，每行包含 M 个字符，表示房间的结构。. 为空地，X 为雕像。
输出
一行，包含一个数，表示最少需要的妖精女仆的数量。
样例输入
样例一：
5 5 1 1
XXXXX
X....
XXX..
X....
XXXXX
样例二：
5 5 2 2
.X.X.
XX..X
.X.X.
...X.
.X.XX
样例输出
样例一：4
样例二：2
提示
•对于分值为 40 的子任务 1，保证 N, M ≤ 10
•对于分值为 20 的子任务 2，保证 N, M ≤ 15
•对于分值为 40 的子任务 3，保证 N ≤ 15, M ≤ 200。
解题思路
数据范围很小，一时想不到解决办法，那就尝试暴力。
行的范围比较小，那就暴力枚举每一行是否使用女仆，即n个格子填0和1，时间复杂度是O(2^n)，接着列就可以贪心了。
在行确定后，如果该列需要清理，那就必须清理，清理连续c列后，继续往后找要清理的地方，需要遍历矩阵，算法复杂度O(n*m)。
总的时间复杂度是O(m*n*2^n)不超时。
程序实现
优化一下：复杂度乘以m*n，不要每一行都看，只看需要清理的行就行，可以预处理将要清理的行保存到数组f：
