Time Limit: 10 Sec Memory Limit: 259 MB
Description
lanzerb的部落在A国的上部，他们不满天寒地冻的环境，于是准备向A国的下部征战来获得更大的领土。 A国是一
个M*N的矩阵，其中某些地方是城镇，某些地方是高山深涧无人居住。lanzerb把自己的部落分成若干支军队，他们
约定：
1. 每支军队可以从任意一个城镇出发，并只能从上往向下征战，不能回头。
途中只能经过城镇，不能经过高山深涧。
2. 如果某个城镇被某支军队到过，则其他军队不能再去那个城镇了。
3. 每支军队都可以在任意一个城镇停止征战。
4. 所有军队都很奇怪，他们走的方法有点像国际象棋中的马。
不过马每次只能走1*2的路线，而他们只能走R*C的路线。
lanzerb的野心使得他的目标是统一全国，但是兵力的限制使得他们在配备人手时力不从心。假设他们每支军队都
能顺利占领这支军队经过的所有城镇，请你帮lanzerb算算至少要多少支军队才能完成统一全国的大业。
Input第一行包含4个整数M、N、R、C，意义见问题描述。
接下来M行每行一个长度为N的字符串。
如果某个字符是'.'，表示这个地方是城镇；如果这个字符时'x'，表示这个地方是高山深涧。
1<=M,N<=50，1<=R,C<=10。
Output输出一个整数，表示最少的军队个数。
Sample Input【样例输入一】
3 3 1 2
...
.x.
...
【样例输入二】
5 4 1 1
....
..x.
...x
....
x...
【样例输出一】
4
【样例输出二】
5
/**************************************************************
Problem: 2150
User: ictsing
Language: C++
Result: Accepted
Time:588 ms
Memory:80824 kb
****************************************************************/
//BZOJ2150 部落战争
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int mt = 2600 + 5;
int f[mt][mt],a[mt][mt],match[mt],num[mt][mt];
bool vis[mt];
int dx[5],dy[5];
char s[500+5];
int n,m,r,c,sum,ans,id;
inline int read()
{
int num=0,flag=1;
char ch;
do{
ch=getchar();
if(ch=='-') flag=-1;
}while(ch<'0'||ch>'9');
do{
num=num*10+ch-'0';
ch=getchar();
}while(ch>='0'&&ch<='9');
return num*flag;
}
bool find(int u)
{
for(int v=1;v<=id;v++)
if(a[u][v]&&!vis[v])
{
vis[v]=1;
if(!match[v]||find(match[v]))
{ match[v]=u;return 1;}
}
return 0;
}
int main()
{
n=read(),m=read(),r=read(),c=read();
id=0;
for(int i=1;i<=n;i++)
{
scanf("%s",s);
for(int j=0;j<m;j++)
if(s[j]=='.') f[i][j+1]=1,num[i][j+1]=++id;
else f[i][j+1]=0;
}
dx[0]=r,dx[1]=r,dx[2]=c,dx[3]=c;
dy[0]=c,dy[1]=-c,dy[2]=r,dy[3]=-r;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(f[i][j])
for(int k=0;k<4;k++)
{
int x=i+dx[k],y=j+dy[k];
if(x<1||x>n||y<1||y>m) continue;
if(f[x][y]) a[num[i][j]][num[x][y]]=1;
}
for(int i=1;i<=id;i++)
{
memset(vis,0,sizeof(vis));
if(find(i)) ans++;
}
printf("%d\n",id-ans);
return 0;
}
评论