web analytics

poj2226 Muddy Fields 二分图匹配

Description

Rain has pummeled the cows' field, a rectangular grid of R rows and C columns (1 <= R <= 50, 1 <= C <= 50). While good for the grass, the rain makes some patches of bare earth quite muddy. The cows, being meticulous grazers, don't want to get their hooves dirty while they eat.

To prevent those muddy hooves, Farmer John will place a number of wooden boards over the muddy parts of the cows' field. Each of the boards is 1 unit wide, and can be any length long. Each board must be aligned parallel to one of the sides of the field.

Farmer John wishes to minimize the number of boards needed to cover the muddy spots, some of which might require more than one board to cover. The boards may not cover any grass and deprive the cows of grazing area but they can overlap each other.

Compute the minimum number of boards FJ requires to cover all the mud in the field.
Input

* Line 1: Two space-separated integers: R and C

* Lines 2..R+1: Each line contains a string of C characters, with '*' representing a muddy patch, and '.' representing a grassy patch. No spaces are present.
Output

* Line 1: A single integer representing the number of boards FJ needs.
Sample Input

4 4
*.*.
.***
***.
..*.
Sample Output

4
Hint

OUTPUT DETAILS:

Boards 1, 2, 3 and 4 are placed as follows:
1.2.
.333
444.
..2.
Board 2 overlaps boards 3 and 4.

题目大意:
给出 n,m
然后再给出一个n*m的字符矩阵。
其中"*"代表泥土什么的"."代表水。
我们需要用最少的木板来覆盖这个泥土地,不能覆盖到水。
每个木板宽1但是无限长。
木板之间可以重叠。

分析:
矩阵。无限长木板。我们首先就可以想到。我需要来判断,我某一个点到底是横着放木板。还是竖着放木板。
所以这里可以用二分图来解决这个匹配问题。

在二分图这个模型里。
可以横着的木板看作一个集合。可以竖着放的木板看作另一个集合。
如果某一个横着的木板如果和某一个竖着放的木板重合,该亮点连边。
而我们就需要求一个二分图的最小点覆盖。
由于二分图最大匹配==二分图最小点覆盖。

这道题建完图跑一个二分图最大匹配就好了。

Post a Comment

You must be logged in to post a comment.