- 时间限制: 1 s
- 空间限制: 128000 KB
- 题目等级 : 大师 Master
题目描述 Description
有一个N×M的单位方格中，其中有些方格是水塘，其他方格是陆地。如果要用1×2的矩阵区覆盖（覆盖过程不容许有任何部分重叠）这个陆地，那么最多可以覆盖多少陆地面积。 
输入描述 Input Description
输入文件的第一行是两个整数N，M (1<=N，M<=100)，第二行为一个整数K(K<=50)，接下来的K行，每行两个整数X，Y表示K个水塘的行列位置。(1<=X<=N,1<=Y<=M) 。
输出描述 Output Description
输出所覆盖的最大面积块（1×2面积算一块）。
样例输入 Sample Input
4 4
6
1 1
1 4
2 2
4 1
4 2
4 4样例输出 Sample Output
4 题解：
对于每个空格，向它的上下左右连一条边，跑一遍匈牙利算法就好。
#include <iostream>
using namespace std;
int n, m, k, ans;
bool g[105][105], lian[10005], used[10005], line[10005][10005];
int hash(int x, int y)
{
return (x - 1) * m + y;
}
bool find(int x)
{
int xl, xh;
if(x % m)
{
xl = x % m;
xh = x / m + 1;
}
else
{
xl = m;
xh = x / m;
}
if(g[xh][xl])
return false;
for (int i = 1; i <= n * m; ++i)
if (line[x][i] && !used[i])
{
used[i] = true;
if(lian[i] == 0 || find(lian[i]))
{
lian[i] = x;
return true;
}
}
return false;
}
int main()
{
int h, l;
cin >> n >> m >> k;
for (int i = 0; i < k; ++i)
{
cin >> h >> l;
g[h][l] = true;
}
int ih, il;
for (int i = 1; i <= n * m; ++i)
{
if(i % m)
{
il = i % m;
ih = i / m + 1;
}
else
{
il = m;
ih = i / m;
}
if (!g[ih][il])
{
if (ih > 1)
if (!g[ih - 1][il])
line[i][i - m] = true;
if (il > 1)
if (!g[ih][il - 1])
line[i][i - 1] = true;
if (ih < n)
if (!g[ih + 1][il])
line[i][i + m] = true;
if (il < m)
if (!g[ih][il + 1])
line[i][i + 1] = true;
}
}
unsigned ans = 0;
for (int i = 1; i <= n * m; ++i)
{
for (int j = 1; j <= n * m; ++j)
used[j] = false;
if (find(i))
++ans;
}
cout << ans / 2;
}