lanzerb的部落在A国的上部，他们不满天寒地冻的环境，于是准备向A国的下部征战来获得更大的领土。 A国是一个M*N的矩阵，其中某些地方是城镇，某些地方是高山深涧无人居住。lanzerb把自己的部落分成若干支军队，他们约定： 1. 每支军队可以从任意一个城镇出发，并只能从上往向下征战，不能回头。途中只能经过城镇，不能经过高山深涧。 2. 如果某个城镇被某支军队到过，则其他军队不能再去那个城镇了。 3. 每支军队都可以在任意一个城镇停止征战。 4. 所有军队都很奇怪，他们走的方法有点像国际象棋中的马。不过马每次只能走1*2的路线，而他们只能走R*C的路线。 lanzerb的野心使得他的目标是统一全国，但是兵力的限制使得他们在配备人手时力不从心。假设他们每支军队都能顺利占领这支军队经过的所有城镇，请你帮lanzerb算算至少要多少支军队才能完成统一全国的大业。

第一行包含4个整数M、N、R、C，意义见问题描述。接下来M行每行一个长度为N的字符串。如果某个字符是'.'，表示这个地方是城镇；如果这个字符时'x'，表示这个地方是高山深涧。

输出一个整数，表示最少的军队个数。

【样例输出二】
5
【样例说明】

【数据范围】
100%的数据中，1<=M,N<=50，1<=R,C<=10。

#include<cstdio>

#include<vector>

#include<cstring>

int m,n,r,c,ans=,N=;

char ch;

bool g[][]={};//(x-1)*n+y

bool vis[]={};

struct men{

    int lover;

    std::vector<int> t;

}man[];

int woman[]={};

bool dfs(int u)

{

    int sz=man[u].t.size();

    for(int i=;i<sz;i++)

    {

        int w=man[u].t[i];

        if(!vis[w])

        {

            vis[w]=;

            if(!woman[w]||dfs(woman[w]))

            {

                woman[w]=u;

                man[u].lover=w;

                return ;

            }

        }

    }

    return ;

}

int main()

{

    //freopen("lanzerb.in","r",stdin);

    //freopen("lanzerb.out","w",stdout);

    scanf("%d %d %d %d",&m,&n,&r,&c);

    for(int i=;i<=m;i++)

    {

        for(int j=;j<=n;j++)

        {

            scanf("\n%c",&ch);

            if(ch=='.')

                g[i][j]=,N++;

        }

    }

    int bh[][]={{r,c},{c,-r},{c,r},{r,-c}};

    for(int i=;i<=m;i++)

    {

        for(int j=;j<=n;j++)

        {

            if(!g[i][j]) continue;

            int id=(i-)*n+j;

            for(int k=;k<;k++)

            {

                if(r==c&&k>) break;

                int x=i+bh[k][],y=j+bh[k][];

                if(x>=&&x<=m&&y>=&&y<=n&&g[x][y])

                {

                    man[id].t.push_back((x-)*n+y);

                }

            }

        }

    }

    memset(woman,,sizeof(woman));

    for(int i=;i<=n*m;i++)

    {

        memset(vis,,sizeof(vis));

        if(dfs(i))

            ans++;

    }

    printf("%d\n",N-ans);

    return ;

}