题目名称	1616. [USACO JAN05]泥泞的牧场
输入输出	`usaco_cover.in/out`
难度等级	★★☆
时间限制	1000 ms (1 s)
内存限制	256 MiB
测试数据	17
题目来源	cstdio 于2014-05-05加入
开放分组	全部用户
提交状态
分类标签	USACO 二分图
	分享题解

通过：102，提交：196，通过率：52.04%
粘粘自喜	100	0.000 s	0.00 MiB	C++
Magic_Sheep	100	0.000 s	0.00 MiB	C++
Hzoi_chairman	100	0.000 s	0.00 MiB	C++
金身人面兽	100	0.000 s	0.00 MiB	C++
Hzoi_chairman	100	0.000 s	0.00 MiB	C++
派特三石	100	0.000 s	0.00 MiB	C++
于	100	0.000 s	0.00 MiB	C++
SOBER GOOD BOY	100	0.000 s	0.00 MiB	C++
千世断魂自凝眉	100	0.000 s	0.00 MiB	C++
槿柒	100	0.000 s	0.00 MiB	C++

关于泥泞的牧场的近10条评论(全部评论)
安呐一条小咸鱼。 2016-06-16 09:21 7楼
数组大小要平方…… 千世断魂自凝眉 2016-06-16 08:34 6楼
居然AK了，真不多见 Hzoi_ 2016-06-16 06:37 5楼
一个代码，歇会新交就过了良心AC maxn要开到510班才能过 Go灬Fire 2016-06-15 15:45 4楼
一個人的雨 2015-08-12 10:33 3楼
同“机器人放置” forever 2015-07-27 21:03 2楼
混谈，果断把N打成M竟然得了70分天一阁 2014-07-31 20:08 1楼

1616. [USACO JAN05]泥泞的牧场

★★☆ 输入文件：usaco_cover.in 输出文件：usaco_cover.out 简单对比
时间限制：1 s 内存限制：256 MiB

【题目描述】

大雨侵袭了奶牛们的牧场。牧场是一个R*C的矩形，其中1<=R,C<=50。大雨将没有长草的土地弄得泥泞不堪，可是小心的奶牛们不想在吃草的时候弄脏她们的蹄子。

为了防止她们的蹄子被弄脏，约翰决定在泥泞的牧场里放置一些木板。每一块木板的宽度为1个单位，长度任意。每一个木板必须放置在平行于牧场边界的泥地里。

约翰想使用最少的木板覆盖所有的泥地。一个木板可以重叠在另一个木板上，但是不能放在草地上。

【输入格式】

第1行：两个整数R和C。

第2到R+1行：每行C个字符，其中“*”代表泥地，“.”代表草地。

【输出格式】

最少需要多少木板。

【样例输入】

4 4
*.*.
.***
***.
..*.

【样例输出】

【提示】

木板的放置方法如下：

1.2.
.333
444.
..2.

木板2和3，4重叠。

【来源】

USACO JAN05 Muddy Fields

Alex Schwendner,2004

译者蒋炎岩