Muddy Fields

POJ 2226

题目来源: POJ

给定一个由*和.组成的二位数组。要求用一些宽为\(1\)，长度任意的木板来覆盖所有的*。求木板数量最少为多少。

第一眼看到这道题，我们便能够想起一个常见的二分图模型: 在二维数组上每一行或每一列覆盖木板，使得所有的特殊点被覆盖。但是这题和这个模型并不完全一样。这道题里的木板只能覆盖在*上，而模型中的则是任意位置。

所以，我们需要做一些改动。我们发现，无论怎样，木板还是会分为横向与纵向，并且满足二分图的模型。那么我们只需要令每一个横向的联通块和纵向的联通块为一个节点即可，而不是把一行或者一列当作节点。

所以我们需要预处理出所有的"节点",然后跑一边匈牙利算法即可。