当前位置:首页 > 搜索 > 深度优先搜索 > 正文
SSOJ3015C十六夜咲夜
2820+

题目大意:一个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:

About

坚决不Copy代码!

本文标签:,,,,,,,,

SSOJ3015C十六夜咲夜:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!