【题目大意】
给出一张图，'*'表示不能走的障碍。已知每只军队可以按照r*c的方向行军，且军队与军队之间路径不能交叉。问占据全部'.'最少要多少支军队？
【思路】
首先注意题意中有说“军队只能往下走”，弄清楚方向。
从某点往它能走的四个点走一趟，连边。最小路径覆盖=总数-二分图最大匹配。
哦耶！老了，连匈牙利的板子都敲错orzzzzzz
#include<bits/stdc++.h>
using namespace std;
const int MAXN=;
int m,n,r,c,maps[MAXN][MAXN];
int lk[MAXN*MAXN],vis[MAXN*MAXN];
vector<int> E[MAXN*MAXN]; int check(int x,int y)
{
if (x>= && x<=m && y>= && y<=n && maps[x][y]) return ;else return ;
} int id(int x,int y){return ((x-)*n+y);} void addedge(int u,int v)
{
E[u].push_back(v);
} int find(int u)
{
for (int i=E[u].size()-;i>=;i--)
{
int v=E[u][i];
if (!vis[v])
{
vis[v]=;
if (!lk[v]|| find(lk[v]))//呜哇这里写成了find(v)半天没有发现，果然是老阿姨了啊
{
lk[v]=u;
return ;
}
}
}
return ;
} void init()
{
scanf("%d%d%d%d",&m,&n,&r,&c);
for (int i=;i<=m;i++)
{
char str[MAXN];
scanf("%s",str);
for (int j=;j<n;j++)
if (str[j]=='.') maps[i][j+]=;else maps[i][j+]=;
}
for (int i=;i<=m;i++)
for (int j=;j<=n;j++)
if (maps[i][j])
{
if (check(i+r,j+c)) addedge(id(i,j),id(i+r,j+c));
if (check(i+r,j-c)) addedge(id(i,j),id(i+r,j-c));
if (check(i+c,j+r)) addedge(id(i,j),id(i+c,j+r));
if (check(i+c,j-r)) addedge(id(i,j),id(i+c,j-r));
}
} void solve()
{
memset(lk,,sizeof(lk));
int sum=,ans=;
for (int i=;i<=m;i++)
for (int j=;j<=n;j++)
{
if (maps[i][j]==)
{
int x=id(i,j);
memset(vis,,sizeof(vis));
sum++;
if (find(x)) ans++;
}
}
printf("%d",sum-ans);
} int main()
{
init();
solve();
}